Advertisement
Guest User

Untitled

a guest
Jan 26th, 2020
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define INF 1e9
  4.  
  5. using namespace std;
  6.  
  7. int nCtr, r, c, cr, cc, nr, nc, src, u, nu, dest, dist[1000000],
  8.     p[1000000], dr[] = {-1,-2,-2,-1,1,2,2,1}, dc[] = {-2,-1,+1,+2,+2,+1,-1,-2};
  9. char cur_move, grid[1000][1001], pmove[1000000], moves[9] = "ABCDEFGH";
  10.  
  11. int main() {
  12.     // freopen("in.txt","rt",stdin);
  13.     // freopen("outMine.txt","wt",stdout);
  14.     scanf("%d",&nCtr);
  15.     for(int x = 0; x < nCtr; x++) {
  16.         scanf("%d%d",&r,&c);
  17.         for(int i = 0; i < r; i++) {
  18.             scanf("%s",grid[i]);
  19.             for(int j = 0; j < c; j++) {
  20.                 if(grid[i][j] == 'K') {
  21.                     src = i * c + j;
  22.                 } else if(grid[i][j] == 'F') {
  23.                     dest = i * c + j;
  24.                 }
  25.             }
  26.         }
  27.         queue<int> q;
  28.         q.push(src);
  29.         fill(dist,dist + r * c,INF);
  30.         fill(p,p + r * c,-1);
  31.         memset(pmove,0,sizeof(pmove));
  32.         dist[u] = 0;
  33.         while(!q.empty()) {
  34.             u = q.front(); q.pop();
  35.             cr = u / c;
  36.             cc = u % c;
  37.             if(u == dest) {
  38.                 break;
  39.             }
  40.             for(int dir = 0; dir < 8; dir++) {
  41.                 nr = cr + dr[dir];
  42.                 nc = cc + dc[dir];
  43.                 nu = nr * c + nc;
  44.                 if(nr >= 0 && nr < r && nc >= 0 && nc < c &&
  45.                     grid[nr][nc] != 'X' && dist[nu] == INF) {
  46.                     dist[nu] = dist[u] + 1;
  47.                     p[nu] = u;
  48.                     pmove[nu] = moves[dir];
  49.                     q.push(nu);
  50.                 }
  51.             }
  52.         }
  53.         if(dist[dest] == INF) {
  54.             printf("Neigh\n");
  55.         } else {
  56.             printf("Whinny\n");
  57.             stack<char> s;
  58.             u = dest;
  59.             while(grid[u / c][u % c] != 'K') {
  60.                 s.push(pmove[u]);
  61.                 u = p[u];
  62.             }
  63.             while(!s.empty()) {
  64.                 cur_move = s.top(); s.pop();
  65.                 printf("%c%s",cur_move,s.empty() ? "\n" : "");
  66.             }
  67.         }
  68.     }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement