题目描述

我们有一个 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
难度：简单
时/空限制：2s / 64MB
总通过数：179
总尝试数：306
来源：Google Kickstart2015 Round D Problem A
算法标签

算法1

C++ 代码

#include<stdio.h>
#include<cstring>
#include<queue>
#include<iostream>
#define N 110
using namespace std;
int t,r,c,n;
char caozuo;
char map[N][N],st[N][N];
int dxy[4][2]={0,1,0,-1,1,0,-1,0};
struct Node{
    int x;
    int y;
}node;
queue<Node>q;
void bfs(int x1,int y1){
    q.push({x1,y1});
    st[x1][y1]=1;
    while(!q.empty()){
        node=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=node.x+dxy[i][0];
            int yy=node.y+dxy[i][1];
            if(xx<0||yy<0||xx>=r||yy>=c)continue;
            if(st[xx][yy]||map[xx][yy]=='0')continue;
            q.push({xx,yy});
            st[xx][yy]=1;
        }
    }
}
int main(){
    int cnt=0;
    int n1,n2,n3;
    scanf("%d",&t);
    while(t--){
        cnt++;
        printf("Case #%d:\n",cnt);
        memset(st,0,sizeof(st));
        scanf("%d %d",&r,&c);
        for(int i=0;i<r;i++)scanf("%s",map[i]);
        scanf("%d",&n);
        getchar();
        for(int i=1;i<=n;i++){
            scanf("%c",&caozuo);
            getchar();
            if(caozuo=='Q'){
                int ans=0;
                memset(st,0,sizeof(st));
                for(int i=0;i<r;i++)
                   for(int j=0;j<c;j++) 
                     if(map[i][j]=='1'&&!st[i][j]){
                         ans++;//表明有几个连通块
                         bfs(i,j);
                     }
                printf("%d\n",ans);          
            }
            if(caozuo=='M'){
                scanf("%d %d %d",&n1,&n2,&n3);
                getchar();
                map[n1][n2]=n3+'0';
            }

            }
        }
    return 0;
}