https://www.luogu.org/problem/P1141
#include<bits/stdc++.h>//最喜欢的万能头 using namespace std; int n,m; char a[1005][1005];//注意一定要开char，否则会炸，后果自负 int b[1005][1005];//记录有没有走过 int i,j,ans[100005];//记录答案 int x,y;//提供的下标 int mx[4]={0,0,1,-1};//四个方向寻找 int my[4]={1,-1,0,0}; void dfs(int x,int y,int p,int i){ if(x<0||x>=n||y<0||y>=n||b[x][y]!=-1||a[x][y]-48!=p)//如果不在范围内，或是找过或是数字不正确 return; b[x][y]=i;//这一步很关键，下面叙述 ans[i]++;//加一个点 for(int k=0;k<4;k++){ int kx=x+mx[k]; int ky=y+my[k]; dfs(kx,ky,!p,i);//dfs常用套路， !p是为了变换数字 } } int main(){ cin>>n>>m; for(i=0;i<n;i++) scanf("%s",&a[i]); memset(b,-1,sizeof(b));//清空 for(i=0;i<m;i++){ cin>>x>>y;//输入 x--,y--;//因为数组从0开始读，给的下标从1开始 if(b[x][y]==-1) dfs(x,y,a[x][y]-48,i);//符合条件就dfs else ans[i]=ans[b[x][y]];//最关键的一步！！如果已经走过，意味着本轮搜索结束，答案就是上一步的i，也就是b数组存在的第二意义。（承接上文b[x][y]=i;） } for(i=0;i<m;i++) cout<<ans[i]<<endl;//完美输出 return 0; } /*因为ASC码48就是'0'，也就是说'0'的值是48，而后依次是'1'到'9' 如果不减去，会超出n， 这样正好是char型减去48就是它对应的int值 */
#include<bits/stdc++.h> using namespace std; int b[1001][1001],c[1001];//b是标记哪个点是属于哪个染色区,c是每个染色区的连通块个数 char a[1001][1001];//a是矩阵 int xx[5] = {0,1,-1,0,0},yy[5] = {0,0,0,1,-1}; int n,m, tot, ku = 1;//tot是统计连通块的, ku是染色区的"名称" void ss(int x,int y) { tot ++; for(int i = 1; i <= 4; i++) { int x2 = x + xx[i],y2 = y + yy[i]; if(a[x][y] != a[x2][y2] && b[x2][y2] == 0 && x2 <= n && x2 > 0 && y2 <= n && y2 > 0 ) { //这里要注意,染过的就不能再染了,想想为什么 b[x2][y2] = ku;//染色 ss(x2,y2); } } return; } int main() { cin>>n>>m; for(int i = 1; i <= n; ++i) scanf("%s",a[i]+1); //输入一整行 for (int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(b[i][j] == 0) { b[i][j] = ku;//起点也要染色 ss(i,j); c[ku] = tot; tot = 0;//清空 ku ++;//换一个连通块的名称 } } } for(int i = 1; i <= m; i++) { int x,y; scanf("%d%d",&x,&y); cout<<c[b[x][y]]<<endl; } return 0; }