P1141 01迷宫
_Birdly_
·
·
个人记录
这是一道 不很正经的 搜索题，个人认为这种一条一条遍历的还是 bfs 用起来舒服。
题意解读
先输入一个宽为 n 的迷宫，只由 1 和 0 组成，这让人不由自主想到用 char 来输入。然后给出 m （稍后代码用 t 代替）组 x 和 y 。求出从这个坐标能走多少步，由题意可知，只有上下左右四周的方格与自己不同且不超出范围时才可以走。
坑点 （重点）
看上去，这道题人畜无害，就是一道普通 bfs 。但是当你看到这句话：
------------
## 坑点处理方法
$m$ 如此大的数量，而 $n$ 相对 $m$ 却又那么小，我们可以想到，这 $m$ 组坐标一定会有相同路径！
那么我们就可以想到，在迷宫中，所有的路径的每一点所能到达的点的数量都是这条路径的长度！
### 毕竟：条条大路通罗马，意味着罗马通着条条大路！
这样，将每个点所在路径的长度都存到整数数组 $anss$ 中，$anss_{i,j}$ 所存的就是所在路径的长度！
最后输入每组 $x,y$ ，我们就可以直接输出 $anss_{x,y}$ 。
------------
# Code Time
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,t,bx,by,k=2;
int tx[]={0,-1,0,1},ty[]={-1,0,1,0};//四个方向不必多说
bool vis[1005][1005];//基本 bfs 需要
char mapp[1005][1005];//基本 bfs 需要
int ansxy[1000010][2],anss[1005][1005];
//重点！ ansxy 中存着一条路径的每一个点，而 anss 则是存每点所在路径的长度
void bfs(int ix,int iy){
k=2;
queue<int> x,y;
x.push(ix),y.push(iy);
ansxy[1][0]=ix,ansxy[1][1]=iy;
while(!x.empty()){//不空不停
int xx=x.front(), yy=y.front();
for(int i=0;i<4;i++)//基本 bfs 操作
if(mapp[xx+tx[i]][yy+ty[i]]!=mapp[xx][yy]&&!vis[xx+tx[i]][yy+ty[i]]&&
xx+tx[i]>=1&&xx+tx[i]<=n&&yy+ty[i]>=1&&yy+ty[i]<=n){
vis[xx+tx[i]][yy+ty[i]]=1;
ansxy[k][0]=xx+tx[i],ansxy[k++][1]=yy+ty[i];
//将点的位置记录下来
x.push(xx+tx[i]), y.push(yy+ty[i]);
}
x.pop(),y.pop();
}
for(int i=1;i<k;i++)//放入路径长度
anss[ansxy[i][0]][ansxy[i][1]]=k-1;//次数点的个数即为路径长度
}
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mapp[i][j];
//从头到尾遍历一遍：遇到没访问过的（即还没有被某条路径包含）的开始 bfs
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!vis[i][j]){
vis[i][j]=1;
bfs(i,j);
}
while(t--){
cin>>bx>>by;
cout<<anss[bx][by]<<endl;
}
return 0;
}
```