题目描述

我们有一个 R
行 C
列的矩形网格，其中每个方格内的数字都是 0
或 1
。

我们将在网格上执行 N
个操作，每个操作都是以下之一：

操作 M
：将网格的一个单元格中的数字更改为 0
或 1
。
操作 Q
：确定 1
的不同连通区域的数量。 1
的连通区域是指矩阵内全部为 1
的连通的单元格的子集，在子集区域内通过沿着共享边缘在单元格之间行进，可以从该区域中的任何单元格到达该区域中的任何其他单元格。
输入格式
第一行包含整数 T
，表示共有 T
组测试数据。

每组数据第一行包含两个整数 R
和 C
，表示矩形网格的行数和列数。

接下来 R
行，每行包含一个长度为 C
的由 1
和 0
构成的字符串，表示矩阵网格的初始状态。

接下来一行，包含整数 N
，表示操作数量。

接下来 N
行，每行包含一个操作指令，操作指令共两种，如下所示：

M x y z，表示 M
指令，具体含义为将第 x
行第 y
列的方格内的值变为 z
。
Q，表示 Q
指令，表示进行一次询问。
输出格式
对于每组测试数据，第一行输出 Case #x:，其中 x
为组别编号（从 1
开始）。

接下来 Q
行，每行输出一个询问的结果。

bfs

C++ 代码

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int t, n, m, k;
char g[N][N];
bool st[N][N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

int bfs()
{
    memset(st, 0, sizeof st);

    int res = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            if (!st[i][j] && g[i][j] == '1')
            {
                res += 1;
                queue<PII> q;
                q.push({i, j});
                st[i][j] = true;
                while (q.size())
                {
                    auto t = q.front();
                    q.pop();

                    for (int i = 0; i < 4; ++i)
                    {
                        int a = t.x + dx[i], b = t.y + dy[i];
                        if (a < 0 || a >= n || b < 0 || b >= m) continue;
                        if (g[a][b] == '0') continue;
                        if (st[a][b]) continue;

                        q.push({a, b});
                        st[a][b] = true;
                    }
                }
            }
        }
    return res;
}

int main()
{
    cin >> t;
    int cnt = 0;
    while (t--)
    {
        cnt ++;
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
                cin >> g[i];

        cin >> k;
        // cout << k;
        char op[2];
        cout << "Case #" << cnt << ": " << endl;
        while (k--)
        {
            cin >> op;
            // cout << op << endl;
            if (op[0] == 'Q') cout << bfs() << endl;
            else 
            {
                int x, y;
                char z;
                cin >> x >> y >> z;
                g[x][y]  = z;
            }
        }


    }

    return 0;
}

```