求连通块的数量

1113. 红与黑

bfs模板

bool 数组记录
while (queue.size()) // 队列不空
{
    // 取出队头
    PII t = q.front();
    q.pop();

    // 枚举4个方向
    for (int i = 0; i < 4; i ++ )
    {
        int x = t.x + dx[i], y = t.y + dy[i];
        // 判断是否在界内
        if (x >=0 && x < n && y >= 0 && y < m && bool数组判断重复元素 && 题目条件其他条件)
        {
            // 题目的要求
            q.push({x, y});// 拓展队尾
        }
    }
}

BFS

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
const int N = 30;
int n, m;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char g[N][N];

void bfs(int s, int e)
{

    int st[N][N];
    memset(st, -1, sizeof st);
    int cnt = 0;
    queue<PII> q;
    st[s][e] = true;
    q.push({s, e});

    while (q.size())
    {
        PII t = q.front();
        q.pop();
        cnt ++;

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && st[x][y] != 0 && g[x][y] == '.')
            {
                st[x][y] = 0;
                q.push({x, y});
            }
        }
    }
    cout << cnt << endl;
}

int main ()
{
    while (cin >> m >> n, n, m)
    {
        int start = -1, end = -1;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                cin >> g[i][j];
                if (g[i][j] == '@')
                    start = i, end = j;
            }
        bfs(start, end);
    }
    return 0;
}

DFS

dfs模板

// 起始元素标记一下

// 枚举四个四个方向
for (int i = 0; i < 4; i ++ )
{
    int x = start + dx[i], y = end + dy[i];
    if (x >= 0 && x < n && y >= 0 && y < m && 判断条件)
        dfs(x, y);
}

#include <iostream>

using namespace std;

const int N = 25;
char g[N][N];
int n, m;
int res;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dfs(int x, int y)
{
    int res = 0;
    g[x][y] = '#';
    res ++;
    for (int i = 0; i < 4; i ++ )
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m && g[tx][ty] == '.')
        {
            res += dfs(tx, ty);
        }
    }
    return res;
}

int main ()
{
    while (cin >> m >> n, n || m)
    {
        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                cin >> g[i][j];
                if (g[i][j] == '@')
                    x = i, y = j;
            }
        cout << dfs(x, y) << endl;
    }
    return 0;
}