首页 > 代码库 > 盲目的毛驴和老虎 donkeytiger
盲目的毛驴和老虎 donkeytiger
【题目描述】：
在中国的贵州省没有驴子。一个麻烦制造者运了一头毛驴，并把它放在森林中，森林可视为一个N*N的网格。左上角坐标(0,0)，右下角坐标(n-1,n-1)。前一个数字是行号，后一个是列号。
驴子过着幸福的生活，直到它远远的看见一只老虎。驴子从来没有见过老虎，老虎也从来没有见过驴子。他们两个都害怕，想逃避对方。所以他们开始跑得很快。因为他们害怕，他们以一种没有任何意义的方式开跑。他们每一步都移动到在他们的运行方向上的下一个格子，但他们不能离开森林。因为他们都想去新的地方，驴子永远不会进入一个已经被自己访问的格子，老虎也采取同样的方式。驴子和老虎开始时都是随机一个方向跑，他们总是有相同的速度。他们不会改变他们的方向，直到他们不能再向前跑了。如果他们不能再往前走了，他们立刻改变了方向。当改变方向时，驴子总是向右转，老虎总是向左拐。如果他们转弯，仍然不能继续前进，他们会停止运行，并留在他们的地方，而不试图再向下一个方向转弯。现在给出他们的起始位置和方向，如果驴和老虎能在同一个格子里面相遇，则输出坐标，否则输出-1 。
【输入描述】：
输入有几个测试用例。在每个测试用例中：
第一行是一个整数n，这意味着森林是一个N*N的网格。
第二行包含三个整数R，C和D，这意味着，驴开始在格子（R，C），D是开跑的方向，可以是0，1，2或3。0意味着东方，1意味着南方，2意味着西方，3意味着北（上为北）。
第三行格式相同，它指的是老虎。
最后一行以一个0结束。
【输出描述】：
对于每一个测试，输出它们第一次相遇的单元的坐标，如果不能相遇输出-1。
【样例输入】 | 【样例输出】 |
2 0 0 0 0 1 2 4 0 1 0 3 2 0 0 | -1 1 3 |
【数据范围及描述】：
2 <= N <= 1000, 0 <= R, C < N
这是一道模拟题，形式上类似于搜索。
只提一点：注意一开始就在一起的情况！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn=1005; 8 const int dx[]={0,1,0,-1}; 9 const int dy[]={1,0,-1,0};10 int N;11 int R1,C1,D1,R2,C2,D2;12 bool V1[maxn][maxn],V2[maxn][maxn];13 14 void work()15 {16 memset(V1,false,sizeof(V1));17 memset(V2,false,sizeof(V2));18 int x1(R1),x2(R2),y1(C1),y2(C2),z1(D1),z2(D2);19 V1[x1][y1]=true;V2[x2][y2]=true;20 bool f1,f2;21 f1=f2=true;22 while(f1||f2)23 {24 if(x1==x2&&y1==y2)25 {26 printf("%d %d\n",x1,y1);27 return;28 }29 if(f1)30 {31 int xx=x1+dx[z1];32 int yy=y1+dy[z1];33 if(xx<0||xx>=N||yy<0||yy>=N||V1[xx][yy])34 {35 z1=(z1+1)%4;36 xx=x1+dx[z1];37 yy=y1+dy[z1];38 if(xx<0||xx>=N||yy<0||yy>=N||V1[xx][yy]) f1=false;39 else40 {41 V1[xx][yy]=true;42 x1=xx;y1=yy;43 }44 }45 else46 {47 V1[xx][yy]=true;48 x1=xx;y1=yy;49 }50 }51 if(f2)52 {53 int xx=x2+dx[z2];54 int yy=y2+dy[z2];55 if(xx<0||xx>=N||yy<0||yy>=N||V2[xx][yy])56 {57 z2=(z2+3)%4;58 xx=x2+dx[z2];59 yy=y2+dy[z2];60 if(xx<0||xx>=N||yy<0||yy>=N||V2[xx][yy]) f2=false;61 else62 {63 V2[xx][yy]=true;64 x2=xx;y2=yy;65 }66 }67 else68 {69 V2[xx][yy]=true;70 x2=xx;y2=yy;71 }72 }73 }74 cout<<-1<<endl;75 return;76 }77 78 int main()79 {80 while(scanf("%d",&N)!=EOF)81 {82 if(N==0) break;83 scanf("%d %d %d",&R1,&C1,&D1);84 scanf("%d %d %d",&R2,&C2,&D2);85 work();86 }87 return 0;88 }
盲目的毛驴和老虎 donkeytiger