AOJ 1046 Ghost Buster!
問題
解法
BFSで解ける。リンレンの双子の問題はバグ埋め込んでなかなかACでなかったけど、今回は一発AC。全探索の実装なれてきたのかな
心臓に悪いコード
int dy[] = {0, -1,0,1,0}, dx[] = {0, 0,-1,0,1}; int gdy[] = {0, 0, 1, 0, 0, 0, 0, 0, -1}, gdx[] = {0, 0, 0, 0, -1, 0, 1, 0, 0}; int H, W; char field[32][32], pattern[16]; P nexta(int y, int x, int d){ int ny = y+dy[d], nx = x+dx[d]; ny = max(0, min(H-1, ny)); nx = max(0, min(W-1, nx)); if(field[ny][nx] == '#'){ ny = y; nx = x; } return MP(ny, nx); } P nextb(int y, int x, int c){ int L = strlen(pattern); int ny = y+gdy[pattern[c%L]-'0'], nx = x+gdx[pattern[c%L]-'0']; ny = max(0, min(H-1, ny)); nx = max(0, min(W-1, nx)); return MP(ny, nx); } int main(){ while(scanf("%d%d", &H, &W) && H+W){ rep(i, H) scanf("%s", field[i]); scanf("%s", pattern); int ay, ax, by, bx; rep(i, H) rep(j, W){ if(field[i][j] == 'A'){ ay = i; ax = j;} else if(field[i][j] == 'B'){ by = i; bx = j;} } queue<pair<int, pipi> >q; map<pair<pipi, int>, int>m; q.push(MP(0, MP(MP(ay, ax), MP( by, bx)))); m[MP(MP(MP(ay, ax), MP(by, bx)), -1)] = 1; while(!q.empty()){ pair<int, pipi> now = q.front(); q.pop(); if(now.AY == now.BY && now.AX == now.BX){ printf("%d %d %d\n", now.F, now.AY, now.AX); goto e; } rep(d, 5){ P na = nexta(now.AY, now.AX, d); P nb = nextb(now.BY, now.BX, now.F); if(m.count(MP(MP(na, nb), (now.F%strlen(pattern))))) continue; m[MP(MP(na, nb), now.F%strlen(pattern))] = 1; q.push(MP(now.F+1, MP(na, nb))); } } puts("impossible"); e:; } return 0; }
幽霊の移動は配列使ってやったのは、いちいち分岐してメイン関数が読みづらくなるのがイヤだったから。結局、サブルーチンにしたけど。せめて0からはじめたり、1~5とかにしてほしかった