YM_1 @ 2024-07-18 16:36:25
#include <bits/stdc++.h>
using namespace std;
int n,m,ma[1000][10000],book[1000][10000];
struct node{
int x,y,step;
}q[101011000];
int bfs(int sx,int sy){
int head=0,tail=0;
q[tail].x=sx;
q[tail].y=sy;
q[tail].step=ma[sx][sy];
int sum=1;
book[sx][sy]=1;
tail++;
int nex[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
while(head<tail){
node h=q[head];
for(int k=0;k<4;k++){
int tx=h.x+nex[k][0];
int ty=h.y+nex[k][1];
if(tx<1||tx>n||ty<1||ty>n)
continue;
if(book[tx][ty])
continue;
if((ma[tx][ty]==0&&h.step==1)||(ma[tx][ty]==1&&h.step==0)){
sum++;
q[tail].x=tx;
q[tail].y=ty;
q[tail].step=ma[tx][ty];
book[tx][ty]=1;
tail++;
}
}
head++;
}
return sum;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=0;j<n;j++){
ma[i][j+1]=s[j]-'0';
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++)
// cout<<ma[i][j]<<" ";
// cout<<endl;
// }
for(int i=1;i<=m;i++){
int ssx,ssy;
cin>>ssx>>ssy;
memset(book,0,sizeof(book));
int ans=bfs(ssx,ssy);
cout<<ans<<endl;
}
return 0;
}
by YM_1 @ 2024-07-19 16:10:04
@An_Idiot
by An_Idiot @ 2024-07-19 16:17:16
@Zhourenyu0214 已关，诶你也看nor叔啊
by liujiyu2013 @ 2024-07-20 14:10:10
做一个visit数组，用于记录是否遍历（搜）过该元素或该元素的连通块号码（初始建议做成-1，与0区分）。
从图上将每一个字符（数字）遍历过去， 当该元素没有被遍历，就去搜索：DFS 最后m次询问，输出visit[i][j] 就好了
DFS：上下左右都check一下，判断是否出界、是否遍历过、是否不等于当前元素，如果OK，此连通块的个数++，再去往下搜
可以参考我的代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
char mp[1005][1005];
int vis[1005][1005];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int cnt[1005*1005];
int cur;
bool check(int x,int y){
return x>=1 && x<=n && y>=1 && y<=n && vis[x][y]==0;
}
void dfs(int x,int y){
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(check(tx,ty) && mp[x][y]!=mp[tx][ty]){
vis[tx][ty]=cur;//vis[i][j]属于第cur个连通块
cnt[cur]++;//第cur号连通块的元素个数++
dfs(tx,ty);
}
}
return ;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[i][j]==0){//vis[i][j]==0 →(i,j)没被遍历过或搜到过
cur++;
vis[i][j]=cur;
cnt[cur]=1;
dfs(i,j);
}
}
}
while(m--){
int x,y;
cin>>x>>y;
int k=vis[x][y];
cout<<cnt[k]<<"\n";
}
}