1 /*  2     BFS+模拟：dp[i][j][p] 表示走到i，j，方向为p的步数为多少；  3             BFS分4种情况入队，最后在终点4个方向寻找最小值:)  4 */  5 #include 
     
        6 #include 
      
         7 #include 
       
          8 #include 
        
           9 #include 
         
           10 #include 
          
            11 using namespace std; 12 13 const int MAXN = 1e2 + 10; 14 const int INF = 0x3f3f3f3f; 15 int dir[4][4][2] = { 16 { { 0, -1}, { 0, 1}, {-1, 0}, { 1, 0}}, 17 { { 1, 0}, { 0, -1}, { 0, 1}, {-1, 0}}, 18 { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1}}, 19 { { 0, 1}, {-1, 0}, { 1, 0}, { 0, -1}} 20 }; 21 int dp[12][12][4]; 22 int dp2[12][12][4]; 23 int ans[12][12][4]; 24 char maze[12][12]; 25 int sx, sy, ex, ey; 26 int n, m, P; 27 28 bool ok(int nx, int ny, int np) 29 { 30 if (nx < 0 || nx >= n || ny < 0 || ny >= m) return false; 31 if (maze[nx][ny] == '*' || dp[nx][ny][np] != -1) return false; 32 33 return true; 34 } 35 36 void BFS(void) 37 { 38 int x, y, nx, ny, p, np; 39 queue
           
             q; 40 q.push (sx); q.push (sy); q.push (0); 41 42 while (!q.empty ()) 43 { 44 x = q.front (); q.pop (); 45 y = q.front (); q.pop (); 46 p = q.front (); q.pop (); 47 48 if (x == ex && y == ey && ans[x][y][p] == -1) 49 ans[x][y][p] = dp[x][y][p]; 50 51 nx = x + dir[dp[x][y][p]/P%4][p][0]; 52 ny = y + dir[dp[x][y][p]/P%4][p][1]; 53 if (ok (nx, ny, p)) //move robot, not move dir 54 { 55 dp[nx][ny][p] = dp[x][y][p] + 1; 56 q.push (nx); q.push (ny); q.push (p); 57 } 58 59 np = p + 1; 60 if (np > 3) np = 0; 61 if (ok (x, y, np)) //not move robot, move dir to right 62 { 63 dp[x][y][np] = dp[x][y][p] + 1; 64 q.push (x); q.push (y); q.push (np); 65 } 66 67 np = p - 1; 68 if (np < 0) np = 3; 69 if (ok (x, y, np)) //not move robot, move dir to left 70 { 71 dp[x][y][np] = dp[x][y][p] + 1; 72 q.push (x); q.push (y); q.push (np); 73 } 74 75 if (dp[x][y][p] <= 200) //not move 76 { 77 dp[x][y][p]++; 78 q.push (x); q.push (y); q.push (p); 79 } 80 } 81 82 return ; 83 } 84 85 int main(void) //ZOJ 3865 Superbot 86 { 87 //freopen ("F.in", "r", stdin); 88 89 int t; 90 scanf ("%d", &t); 91 while (t--) 92 { 93 memset (dp, -1, sizeof (dp)); 94 memset (ans, -1, sizeof (ans)); 95 96 scanf ("%d%d%d", &n, &m, &P); 97 98 for (int i=0; i