PKU : 3083 - Children of the Candy Corn
問題概要
http://poj.org/problem?id=3083
周りが壁に囲まれた迷路が入力されます.
スタート地点とゴール地点は, 壁際に必ずあります.
このとき, スタート地点から, 左手法と右手法を使って何ステップでゴールにつけるか答えてください.
また, スタートからゴールまでの最短距離も答えてください.
アルゴリズム
左と右の壁ぞいに歩くのは, ただ実装するだけ.
スタートからゴールまでの最短距離は, BFSするだけ.
プログラム
typedef struct{ int x,y,cost; }P; int w,h; int sx,sy,gx,gy; int dx[] = {0,1,0,-1}; int dy[] = {-1,0,1,0}; char t[42][42]; int wall(int dir){ int x = sx, y = sy; int d = (x==0 ? 1 : y==0 ? 2 : x==w-1 ? 3 : 0); int res = 1; while(x != gx || y != gy){ int nd = (d + dir) % 4; int nx = x + dx[nd]; int ny = y + dy[nd]; int nx2 = x + dx[d]; int ny2 = y + dy[d]; if(t[ny][nx] == '.'){ d = nd; x = nx; y = ny; res++; } else if(t[ny2][nx2] == '.'){ x = nx2; y = ny2; res++; } else{ d = (d + dir + 2) % 4; } } return res; } int shortest(){ queue<P> open; bool closed[42][42]; memset(closed,0,sizeof(closed)); P p = {sx,sy,1}; open.push(p); while(!open.empty()){ p = open.front(); open.pop(); if(closed[p.x][p.y]) continue; closed[p.x][p.y] = true; if(p.x == gx && p.y == gy){ return p.cost; } rep(i,4){ int nx = p.x + dx[i]; int ny = p.y + dy[i]; if(t[ny][nx] == '.'){ P np = {nx,ny,p.cost+1}; open.push(np); } } } return -1; } int main(void){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&w,&h); rep(i,h){ scanf("%s",t[i]); rep(j,w){ if(t[i][j] == 'S'){ sx = j; sy = i; t[i][j] = '.'; } else if(t[i][j] == 'E'){ gx = j; gy = i; t[i][j] = '.'; } } } printf("%d %d %d\n",wall(3),wall(1),shortest()); } }