AOJ 1218 Push!!
問題
(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218)
図だけでもなんとか分かるよね。ゴールまで最短で何回動かせばいいか
解法
BFSで動かしていきます。押す方向と逆の方向に人が立てるか、現在いるところからそこにいくことができるかを判定して進めていく。
コード
int w, h; int d[7][7]; int dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0}; map<pi, bool>wm; int check(int ay, int ax, int by, int bx, int cy, int cx){ if(ay == by && ax == bx) return 1; int res = 0; rep(i, 4){ int ny = ay+dy[i], nx = ax+dx[i]; if(ny < 0 || nx < 0 || ny >= h || nx >= w || d[ny][nx] == 1 || wm.count(MP(ny, nx)) || (ny == cy && nx == cx)) continue; wm[MP(ny, nx)] = 1; res += check(ny, nx, by, bx, cy, cx); } return res; } int main(){ while(scanf("%d%d", &w, &h) && w+h){ int y, x, wy, wx; rep(i, h) rep(j, w){ scanf("%d", &d[i][j]); if(d[i][j] == 2){ y = i, x = j; d[i][j] = 0;} if(d[i][j] == 4){ wy = i, wx = j; d[i][j] = 0;} } queue<pair<pi, pi> >q; map<pair<pi, pi>, bool>m; q.push(MP(MP(y, x), MP(wy, wx))); m[MP(MP(y, x), MP(wy, wx))] = 1; int res = 1; while(!q.empty()){ int qsize = (int)q.size(); rep(i, qsize){ pair<pi, pi> now = q.front(); q.pop(); rep(j, 4){ int ny = now.C.Y + dy[j], nx = now.C.X + dx[j]; int nwy = now.C.Y + dy[(j+2)%4], nwx = now.C.X + dx[(j+2)%4]; wm.clear(); wm[MP(now.W.Y, now.W.X)] = 1; if(ny < 0 || nx < 0 || ny >= h || nx >= w || nwy < 0 || nwx < 0 || nwy >= h || nwx >= w || d[ny][nx] == 1 || d[nwy][nwx] == 1 || m.count(MP(MP(ny, nx), MP(nwy, nwx))) || !check(now.W.Y, now.W.X, nwy, nwx, now.C.Y, now.C.X)) continue; if(d[ny][nx] == 3){ printf("%d\n", res); goto e; } q.push(MP(MP(ny, nx), MP(nwy, nwx))); m[MP(MP(ny, nx), MP(nwy, nwx))] = 1; } } res++; } puts("-1"); e:; } return 0; }
他の人の解法が難しくてよく分からない