5. 01迷宫
题目ID：8110必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 131072kB
题目描述
有一个仅由数字0与1组成的N∗N格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）
代码
#include<bits/stdc++.h>
using namespace std;
char mp[1005][1005];
int vis[1005][1005];
int cnt[5005];
int n,m,t,ans;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y){
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||ny<1||nx>n||ny>n||mp[x][y]==mp[nx][ny]||vis[nx][ny])continue;
vis[nx][ny]=1;
ans++;
dfs(nx,ny);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
while(m--){
int x,y;
cin>>x>>y;
if(!vis[x][y]){
t++;
ans=0;
dfs(x,y);
cnt[t]=ans;
}
cout<<cnt[t]<<"\n";
}
return 0;
}
