题目描述

我们有一个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行，每行输出一个询问的结果。

数据范围
1≤T≤10,
1≤R,C≤100,
0≤x<R,
0≤y<C,
0≤z≤1,
1≤N≤1000

样例

输入样例：
1
4 4
0101
0010
0100
1111
7
Q
M 0 2 1
Q
M 2 2 0
Q
M 2 1 0
Q
输出样例：
Case #1:
4
2
2
2

算法

dfs
找出第一个 为 ‘1’ 的字符然后遍历
如果不是2S 就超时了 时间复杂度很高

C++ 代码

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

using namespace std;

const int maxn = 105;
const int N = 1010;
int t; // 表示存在几组测试数据
int r, c; // 表示行列的值
int n; // 表示操作的数量
char q[maxn][maxn]; // 问题数组
int stu[maxn][maxn]; // 表示当前是否被访问过
int res[N];
char h; // 表示对应的操作 handle
int x, y;
char z; // 表示 M操作后 对应的 x y z

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};


void dfs(int x, int y, int  id)
{
    // 返回条件
    if (x < 0 || x >= r || y < 0 || y >= c) return;
    if (stu[x][y] > 0 || q[x][y] != '1')    return;

    stu[x][y] = id; // 连通分量编号
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(tx >= 0 && tx < r && ty >= 0 && ty < c)
                dfs(tx, ty, id);
        }

}

int main()
{
    cin >> t;
    int k = 0;

    while(t--)
    {
        int t1 = 0;
        // 读入初始数组
        cin >> r >> c;
        for (int i = 0; i < r; ++i)
            cin >> q[i];

        cin >> n;
        // 读入操作数
        for(int i = 0; i < n; i++)
        {
            int cnt = 0;
            cin >> h;
            if(h == 'Q')
            {
                for (int i = 0; i < r; i++)
                    for (int j = 0; j < c; j++)
                        if(stu[i][j] == 0 && q[i][j] == '1') dfs(i, j, ++cnt);
                res[t1++] = cnt;
                memset(stu, 0, sizeof stu);
            }
            else 
            {
                // x y 定义为整型， z 为字符型 不然赋值会失败
                cin >> x >> y;
                cin >> z;
                q[x][y] = z;
            }
        }

        cout << "Case #" << ++k << ":" <<endl;
        for (int i = 0; i < t1; i++)
            cout << res[i] << endl;

        memset(res, 0, sizeof res);

    }

    return 0;
}