HDU 4740 The Donkey of Gui Zhou

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define INF 0x3f3f3f3f
15 #define pii pair<int,int>
16 using namespace std;
17 const int maxn = 1005;
18 bool vd[maxn][maxn],vt[maxn][maxn];
19 int n,dx,dy,dr,tx,ty,tr;
20 bool dstop,tstop;
21 const int dir[4][2] = {0,1,1,0,0,-1,-1,0};
22 bool ismeet() {
23     return (tx == dx && ty == dy);
24 }
25 bool isIn(int x,int y) {
26     return (x >= 0 && y >= 0 && x < n && y < n);
27 }
28 bool go() {
29     dstop = false;
30     tstop = false;
31     while(true) {
32         int nx = dx + dir[dr][0];
33         int ny = dy + dir[dr][1];
34         if(!dstop&&isIn(nx,ny) && !vd[nx][ny]) {
35             dx = nx;
36             dy = ny;
37             vd[dx][dy] = true;
38         } else if(!dstop) {
39             int ddr = (dr + 1)%4;
40             nx = dx + dir[ddr][0];
41             ny = dy + dir[ddr][1];
42             if(isIn(nx,ny) && !vd[nx][ny]) {
43                 dx = nx;
44                 dy = ny;
45                 dr = ddr;
46                 vd[dx][dy] = true;
47             } else dstop = true;
48         }
49 
50         nx = tx + dir[tr][0];
51         ny = ty + dir[tr][1];
52         if(!tstop && isIn(nx,ny) && !vt[nx][ny]) {
53             tx = nx;
54             ty = ny;
55             vt[tx][ty] = true;
56         } else if(!tstop) {
57             int ttr = (tr + 3)%4;
58             nx = tx + dir[ttr][0];
59             ny = ty + dir[ttr][1];
60             if(isIn(nx,ny) && !vt[nx][ny]) {
61                 tx = nx;
62                 ty = ny;
63                 tr = ttr;
64                 vt[tx][ty] = true;
65             } else tstop = true;
66         }
67         if(ismeet()) return true;
68         if(tstop && dstop) break;
69     }
70     return false;
71 }
72 int main() {
73     while(scanf("%d",&n),n) {
74         scanf("%d %d %d",&dx,&dy,&dr);
75         scanf("%d %d %d",&tx,&ty,&tr);
76         memset(vd,false,sizeof(vd));
77         memset(vt,false,sizeof(vt));
78         vd[dx][dy] = true;
79         vt[tx][ty] = true;
80         if(tx == dx && dy == ty) {
81             printf("%d %d\n",tx,ty);
82             continue;
83         }
84         if(go()) printf("%d %d\n",tx,ty);
85         else puts("-1");
86     }
87     return 0;
88 }