Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define INF 1e9
- using namespace std;
- int nCtr, r, c, cr, cc, nr, nc, src, u, nu, dest, dist[1000000],
- p[1000000], dr[] = {-1,-2,-2,-1,1,2,2,1}, dc[] = {-2,-1,+1,+2,+2,+1,-1,-2};
- char cur_move, grid[1000][1001], pmove[1000000], moves[9] = "ABCDEFGH";
- int main() {
- // freopen("in.txt","rt",stdin);
- // freopen("outMine.txt","wt",stdout);
- scanf("%d",&nCtr);
- for(int x = 0; x < nCtr; x++) {
- scanf("%d%d",&r,&c);
- for(int i = 0; i < r; i++) {
- scanf("%s",grid[i]);
- for(int j = 0; j < c; j++) {
- if(grid[i][j] == 'K') {
- src = i * c + j;
- } else if(grid[i][j] == 'F') {
- dest = i * c + j;
- }
- }
- }
- queue<int> q;
- q.push(src);
- fill(dist,dist + r * c,INF);
- fill(p,p + r * c,-1);
- memset(pmove,0,sizeof(pmove));
- dist[u] = 0;
- while(!q.empty()) {
- u = q.front(); q.pop();
- cr = u / c;
- cc = u % c;
- if(u == dest) {
- break;
- }
- for(int dir = 0; dir < 8; dir++) {
- nr = cr + dr[dir];
- nc = cc + dc[dir];
- nu = nr * c + nc;
- if(nr >= 0 && nr < r && nc >= 0 && nc < c &&
- grid[nr][nc] != 'X' && dist[nu] == INF) {
- dist[nu] = dist[u] + 1;
- p[nu] = u;
- pmove[nu] = moves[dir];
- q.push(nu);
- }
- }
- }
- if(dist[dest] == INF) {
- printf("Neigh\n");
- } else {
- printf("Whinny\n");
- stack<char> s;
- u = dest;
- while(grid[u / c][u % c] != 'K') {
- s.push(pmove[u]);
- u = p[u];
- }
- while(!s.empty()) {
- cur_move = s.top(); s.pop();
- printf("%c%s",cur_move,s.empty() ? "\n" : "");
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement