题目
一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。
老鼠在迷宫中按照一种固定的方式行走：每个时刻，老鼠都向它所面对的方向前进一格，这需要花费１秒时间。如果前方是一个障碍或者是迷宫的边界，它将花１秒的时间按顺时针方向转90度。
为了抓到老鼠，这只猫决定也按照与老鼠相同的行走方式行进。
猫和老鼠在每个单位时间内是同时行动的。因此，如果猫和老鼠在行进过程中“擦肩而过”，猫是无法捉到老鼠的。只有当猫和老鼠同时到达一个相同的格子时，猫才能捉住老鼠。
初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。
你的任务是编一个程序，求出猫捉到老鼠的所花时间。
Input
输入数据的第一行n，表示输入数据的组数。
每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。
每组输入数据之后均有一个空行作为间隔。
Output
对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。
Sample Input
1*...*...........*......*...*...............*.c....*.....*......*........m......*...*.*.....*.*......
Sample Output
49
思路
很多大佬用的BFS，我开始拿到这题的时候也是条件反射的想到BFS，后来发现不需要BFS，可以用直接法。。。。
注释写的很详细了。
AC代码
#include<iostream>using namespace std;char mp[15][15];int mi,mj,ci,cj,T;int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};int main(){cin>>T;while(T--){for(int i=0;i<10;i++){for(int j=0;j<10;j++){cin>>mp[i][j];if(mp[i][j]=='m'){mi=i,mj=j;// 记录鼠的位置，mp[i][j]='.';// 这个位置是可以再次使用的} if(mp[i][j]=='c'){ci=i,cj=j;mp[i][j]='.';} }}int md=0,cd=0,f=0,t;//md鼠的方向 cd猫的方向for(t=0;t<100000;t++){//如果走了 1e5 次都没有抓到，那就抓不到了int mx = mi+dir[md][0],my = mj+dir[md][1];//鼠往md方向走一格到达的位置if(mx<0 || mx>9 || my<0 || my>9 || mp[mx][my]=='*') md = (md+1)%4;else mi = mx,mj = my;int cx = ci+dir[cd][0],cy = cj+dir[cd][1];if(cx<0 || cx>9 || cy<0 || cy>9 || mp[cx][cy]=='*') cd = (cd+1)%4;//遇到边界或*，转向else ci = cx,cj = cy;//cout<<"t"<<t<<"----m:"<<mi+1<<" "<<mj+1<<" "<<"c:"<<ci+1<<" "<<cj+1<<endl;if(ci == mi && cj == mj){f = 1;break;}}cout<<(f ? t+1 : 0)<<endl；}
如果觉得《Problem 1019 猫捉老鼠（简单题）》对你有帮助，请点赞、收藏，并留下你的观点哦！
