Acwing.643 动态网格
643. 动态网格 - AcWing题库
题号:Acwing.643 动态网格
题目类型:深搜 or 宽搜
简要做题思路:输入:可以用字符串整行读入or数字一个个读入 -> 输入指令 -> 如是M更改对应位置的数字 -> 如是Q循
环遍历数组,深搜寻找每个符合条件的连通块 -> 输出
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int p,r,c,n,g[N][N];
int st[N][N];
char s;
int dx[] ={1,0,-1,0},dy[] = {0,1,0,-1};//偏移量数组
void dfs(int x,int y){
st[x][y] = 1;
for(int i = 0;i < 4;i++){
int nx = x + dx[i],ny = y + dy[i];//使用偏移量枚举上下左右四个方位的1
if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;//盘算是否越界
if(g[nx][ny] == 1 && !st[nx][ny]) {
st[nx][ny] = 1;//标记已经走过
dfs(nx,ny);//继续从该格开始继续深搜
}
}
}
int main(){
cin >> p;
for(int u = 1;u <= p;u++){
memset(st,0,sizeof st);
printf("Case #%d:\n",u);//保证输出格式
//输入
cin >> r >> c;
for(int i = 0;i < r;i++)
for(int j = 0;j < c;j++)
scanf("%01d",&g[i][j]);//每次只读入一个数字
//开始输入字符实现功能
cin >> n;
for(int i = 0;i < n;i++){
cin >> s;
if(s == 'M'){
int x,y,z;
cin >> x >> y >> z;
g[x][y] = z;//按照规则对数组进行修改
}
else{
memset(st,0,sizeof st);
int res = 0;
for(int i = 0;i < r;i++){
for(int j = 0;j < c;j++){
if(g[i][j] == 1 && !st[i][j]){//符合条件+未走过
dfs(i,j);//深搜统计(主要是标记有哪些格子已经走过)
res++;//统计++
}
}
}
cout << res << endl;//输出结果
}
}
}
return 0;
}