P1141 01迷宫
licn
·
·
题解
第一次写，多多指教
01迷宫
题目描述
有一个仅由数字 0 与 1 组成的 n \times n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入格式
有一个仅由数字 0 与 1 组成的 n \times n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输出格式
## 样例 #1
### 样例输入 #1
```
2 2
01
10
1 1
2 2
```
### 样例输出 #1
```
4
4
```
## 提示
所有格子互相可达。
对于 $20\%$ 的数据，$n \leq 10$；
对于 $40\%$ 的数据，$n \leq 50$；
对于 $50\%$ 的数据，$m \leq 5$；
对于 $60\%$ 的数据，$n,m \leq 100$；
对于 $100\%$ 的数据，$n \leq 1000,m \leq 100000$。
本题用bfs，其实就是在问某一点所在**连通块的大小**。我们需要记录每一次询问的点所在连通块的大小，如果后面的询问又在同一个连通块上时可以直接输出。
<https://www.luogu.com.cn/paste/ktflq24v>
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
char a[N][N];//原数组
int n,m,sum=0,quex[N*N],quey[N*N],v[N][N]={0},num=0,h[N*N];//v[][]标记数组，que队列
int dx[4]={0,0,1,-1};//方向数组
int dy[4]={1,-1,0,0};
bool check(int x,int y,int z,int w)
{
if(x<1||x>n||y<1||y>n)return false;
if(v[x][y]==num||a[x][y]==a[z][w])return false;
return true;
}
void bfs(int i,int j)
{
num++;
int l=0,r=0;
quex[++r]=i,quey[r]=j,v[i][j]=num;
while(l<r)
{
int x=quex[++l],y=quey[l];
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(check(xx,yy,x,y))
{
v[xx][yy]=num;
quex[++r]=xx;
quey[r]=yy;
}
}
sum++;
}
h[num]=sum;//记录
cout<<sum<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>(a[i]+1);
for(int i=0;i<m;i++)
{
sum=0;
int x,y;
cin>>x>>y;
if(v[x][y]==0)bfs(x,y);
else cout<<h[v[x][y]]<<endl;
}
return 0;
}