FZU 1019 猫捉老鼠（BFS）

老鼠（BFS）"/>

FZU 1019 猫捉老鼠（BFS）

                                                                      猫捉老鼠

Description

一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。

老鼠在迷宫中按照一种固定的方式行走：每个时刻，老鼠都向它所面对的方向前进一格，这需要花费１秒时间。如果前方是一个障碍或者是迷宫的边界，它将花１秒的时间按顺时针方向转90度。

为了抓到老鼠，这只猫决定也按照与老鼠相同的行走方式行进。

猫和老鼠在每个单位时间内是同时行动的。因此，如果猫和老鼠在行进过程中“擦肩而过”，猫是无法捉到老鼠的。只有当猫和老鼠同时到达一个相同的格子时，猫才能捉住老鼠。
初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。
你的任务是编一个程序，求出猫捉到老鼠的所花时间。

Input

输入数据的第一行n，表示输入数据的组数。
每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。
每组输入数据之后均有一个空行作为间隔。

Output

对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。

Sample Input

1

*...*.....
......*...
...*...*..
..........
...*.c....
*.....*...
...*......
..m......*
...*.*....
.*.*......

Sample Output

49

这道题目一看就觉得是个搜索题，就是把老鼠和猫的路径同时记录，然后用BFS就可以得到他们相遇所需要的步数，那么问题来了，如果相遇不了怎么办？一开始我想了很多，比如他这个路径重复很多次还没相遇，卡死在某段路径上一直重复退出，用两个vst来看他们跑完一圈回到一开始的位置的路径是否相交，不相交就不用管了。但是这些并没有什么用，最最最直接的莫过于，if步数很大很大，就return。并且输出0。这个步数要设置成多大呢。。。10*10=100，让老鼠和猫都跑一百圈，一圈最大步数就是100嘛，所以设置为1万我感觉就可以了（然后我默默地开到一百万过了）

代码如下：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=11;
bool m_vst[maxn][maxn],c_vst[maxn][maxn];
char G[maxn][maxn];
int dir[4][2]={-1,0,0,1,1,0,0,-1};struct State
{int c_x,c_y,m_x,m_y;int c_dir,m_dir;int Step_Counter;bool operator == (const State &a)const{return (c_dir==a.c_dir&&c_x==a.c_x&&c_y==a.c_y&&m_dir==a.m_dir&&m_x==a.m_x&&m_y==a.m_y);}
}t;void bfs(State st)
{bool c_flag=0,m_flag=0,flag;queue <State> q; State now,next; st.Step_Counter=0; c_vst[st.c_x][st.c_y]=1;m_vst[st.m_x][st.m_y]=1;q.push(st);while(!q.empty()){now=q.front(); if(now.c_x==now.m_x&&now.c_y==now.m_y){printf("%d\n",now.Step_Counter);return;}if(now==st&&now.Step_Counter!=0||now.Step_Counter>100000) {printf("0\n");return;}next.c_x=now.c_x+dir[now.c_dir][0]; next.c_y=now.c_y+dir[now.c_dir][1];next.c_dir=now.c_dir;next.Step_Counter=now.Step_Counter+1; if(next.c_x<0||next.c_y<0||next.c_x>=10||next.c_y>=10||G[next.c_x][next.c_y]=='*') {next.c_x=now.c_x;next.c_y=now.c_y;next.c_dir+=1;if(next.c_dir>3)next.c_dir=0;}next.m_x=now.m_x+dir[now.m_dir][0]; next.m_y=now.m_y+dir[now.m_dir][1];next.m_dir=now.m_dir;if(next.m_x<0||next.m_y<0||next.m_x>=10||next.m_y>=10||G[next.m_x][next.m_y]=='*') {next.m_x=now.m_x;next.m_y=now.m_y;next.m_dir+=1;if(next.m_dir>3)next.m_dir=0;}c_vst[next.c_x][next.c_y]++;m_vst[next.m_x][next.m_y]++;q.push(next);q.pop(); }return;
}
int main()
{int T;scanf("%d",&T);while(T--){memset(c_vst,0,sizeof(c_vst));memset(m_vst,0,sizeof(m_vst));for(int i=0;i<10;i++){scanf("%s",&G[i]);for(int j=0;j<10;j++){if(G[i][j]=='c'){t.c_x=i;t.c_y=j;t.c_dir=0;}if(G[i][j]=='m'){t.m_x=i;t.m_y=j;t.m_dir=0;}}}bfs(t);}return 0;
}

其实就是一道普通的BFS题，但是又有点特别，就是这个不相交的终止条件，还是步数如果太大，就退出比较靠谱啊