本文主要是介绍FZU Problem 1019 猫捉老鼠，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem 1019 猫捉老鼠
Accept: 1090 Submit: 3535 Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。
老鼠在迷宫中按照一种固定的方式行走：每个时刻，老鼠都向它所面对的方向前进一格，这需要花费１秒时间。如果前方是一个障碍或者是迷宫的边界，它将花１秒的时间按顺时针方向转90度。
为了抓到老鼠，这只猫决定也按照与老鼠相同的行走方式行进。
猫和老鼠在每个单位时间内是同时行动的。因此，如果猫和老鼠在行进过程中“擦肩而过”，猫是无法捉到老鼠的。只有当猫和老鼠同时到达一个相同的格子时，猫才能捉住老鼠。
初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。
你的任务是编一个程序，求出猫捉到老鼠的所花时间。
Input
输入数据的第一行n，表示输入数据的组数。
每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。
每组输入数据之后均有一个空行作为间隔。
每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。
每组输入数据之后均有一个空行作为间隔。
Output
对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。
Sample Input
1*...*...........*......*...*...............*.c....*.....*......*........m......*...*.*.....*.*......
Sample Output
49
BFS题，构造一下STRUCT 和 VIS 就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<sstream>
#include<cctype>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int maxn=1234;int T;
int n,m;
int ans,flag;
char maps[15][15];
int c[][2]={{-1,0},{0,1},{1,0},{0,-1}};//与自己设定的DIR要配对struct Node
{int x1,y1,x2,y2;int dirc,dirm;//0，1，2，3，分别代表上右下左int step;
} node;bool vis[15][15][5][15][15][5];void bfs()
{queue<Node> q;node.step=0;node.dirc=0;node.dirm=0;vis[node.x1][node.y1][0][node.x2][node.y2][0]=1;q.push(node);while(!q.empty()){Node tmp=q.front(),tp;q.pop();if(tmp.x1==tmp.x2&&tmp.y1==tmp.y2){printf("%d\n",tmp.step);return ;}int cx=tmp.x1+c[tmp.dirc][0];int cy=tmp.y1+c[tmp.dirc][1];int mx=tmp.x2+c[tmp.dirm][0];int my=tmp.y2+c[tmp.dirm][1];if(cx>=0&&cx<10&&cy>=0&&cy<10&&maps[cx][cy]!='*'){tp.dirc=tmp.dirc;tp.x1=cx;tp.y1=cy;}else{tp.dirc=(tmp.dirc+1)%4;tp.x1=tmp.x1;tp.y1=tmp.y1;}if(mx>=0&&mx<10&&my>=0&&my<10&&maps[mx][my]!='*'){tp.dirm=tmp.dirm;tp.x2=mx;tp.y2=my;}else{tp.dirm=(tmp.dirm+1)%4;tp.x2=tmp.x2;tp.y2=tmp.y2;}if(!vis[tp.x1][tp.y1][tp.dirc][tp.x2][tp.y2][tp.dirm]){vis[tp.x1][tp.y1][tp.dirc][tp.x2][tp.y2][tp.dirm]=true;tp.step=tmp.step+1;q.push(tp);}}printf("0\n");
}int main()
{int t;scanf("%d",&t);while(t--){memset(maps,0,sizeof(maps));memset(vis,0,sizeof(vis));for(int i=0; i<10; i++){scanf("%s",maps[i]);for(int j=0;j<10;j++)if(maps[i][j]=='c'){node.x1=i;node.y1=j;}elseif(maps[i][j]=='m'){node.x2=i;node.y2=j;}}bfs();}return 0;
}
这篇关于FZU Problem 1019 猫捉老鼠的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
