hdu 4740 The Donkey of Gui Zhou(暴力搜索)

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=4740

【题意】：

　　森林里有一只驴和一只老虎，驴和老虎互相从来都没有见过，各自自己走过的地方不能走第二次，都会朝着一个方向走，直到这个方向不能走，然后转向，驴只会右转，老虎只会左转，当转过一次之后还是不能往前走，那么它就停下来不再移动了。。。问驴和老虎是否能相遇在一个坐标点。。。

【题解】：

　　暴力搜索，模拟过程就能过，不存在超时问题

【code】：

  1 /*
  2 JudgeStatus:Accepted  time:15MS 
  3 Memory:4212K    codeLenght:2591B 
  4 Language:C++    Author:cj 
  5 */
  6 #include <iostream>
  7 #include <stdio.h>
  8 #include <string.h>
  9 
 10 using namespace std;
 11 #define N 1010
 12 
 13 int mark[N][N];
 14 int n;
 15 
 16 int cx[]={0,1,0,-1};
 17 int cy[]={1,0,-1,0};
 18 int stop1,stop2;
 19 int x,y,flag;
 20 
 21 void solve(int r1,int c1,int d1,int r2,int c2,int d2)
 22 {
 23     int x1,y1,x2,y2;
 24     x1=r1;
 25     y1=c1;
 26     x2=r2;
 27     y2=c2;
 28     while(1)
 29     {
 30         r1=x1,c1=y1,r2=x2,c2=y2;
 31         if(flag) break;
 32         if(!stop1)  //判断驴是否已经停止移动
 33         {
 34             x1=r1+cx[d1];
 35             y1=c1+cy[d1];
 36             if(x1>=0&&x1<n&&y1>=0&&y1<n&&mark[x1][y1]!=1&&mark[x1][y1]!=3)
 37             {
 38                 mark[x1][y1]+=1;
 39             }
 40             else
 41             {
 42                 d1 = (d1+1)%4;
 43                 x1=r1+cx[d1];
 44                 y1=c1+cy[d1];
 45                 if(!(x1>=0&&x1<n&&y1>=0&&y1<n&&mark[x1][y1]!=1&&mark[x1][y1]!=3))
 46                 {
 47                     stop1=1;
 48                     x1=r1;
 49                     y1=c1;
 50                 }
 51                 else
 52                 {
 53                     mark[x1][y1]+=1;
 54                 }
 55             }
 56         }
 57         if(!stop2)  //判断老虎是否已经停止移动
 58         {
 59             x2=r2+cx[d2];
 60             y2=c2+cy[d2];
 61             if(x2>=0&&x2<n&&y2>=0&&y2<n&&mark[x2][y2]!=2&&mark[x2][y2]!=3)
 62             {
 63                 mark[x2][y2]+=2;
 64             }
 65             else
 66             {
 67                 d2 = (d2+3)%4;
 68                 x2=r2+cx[d2];
 69                 y2=c2+cy[d2];
 70                 if(!(x2>=0&&x2<n&&y2>=0&&y2<n&&mark[x2][y2]!=2&&mark[x2][y2]!=3))
 71                 {
 72                     stop2=1;
 73                     x2=r2;
 74                     y2=c2;
 75                 }
 76                 else
 77                 {
 78                     mark[x2][y2]+=2;
 79                 }
 80             }
 81         }
 82         if(x1==x2&&y1==y2) //当老虎和驴相遇
 83         {
 84             x=x1;
 85             y=y1;
 86             flag=1;
 87             return ;
 88         }
 89         if(stop1+stop2==2)  //当老虎和驴都停止移动且不在同一坐标，返回不可达
 90         {
 91             flag=-1;
 92         }
 93     }
 94 }
 95 
 96 int main()
 97 {
 98     while(~scanf("%d",&n)&&n)
 99     {
100         int r1,c1,r2,c2,d1,d2;
101         scanf("%d%d%d",&r1,&c1,&d1);
102         scanf("%d%d%d",&r2,&c2,&d2);
103         memset(mark,0,sizeof(mark));
104         flag=stop1=stop2=0;
105         mark[r1][c1]=1;
106         mark[r2][c2]=2;
107         if(r1==r2&&c1==c2)
108         {
109             printf("%d %d
",r1,c1);
110             continue;
111         }
112         solve(r1,c1,d1,r2,c2,d2);
113         if(flag==-1)
114         {
115             puts("-1");
116         }
117         else
118         {
119             printf("%d %d
",x,y);
120         }
121     }
122     return 0;
123 }