AOJ 0223 Stray Twins
問題
解法
BFS。入力のところで処理の時とy、x座標を逆にあつかっててwa連発。
心臓に悪いコード
int board[51][51], Y, X; int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; pii nextp(pii now, int i, int d){ pii next = now; next.Y += dy[i] * d; next.X += dx[i] * d; if(BW(next.Y, Y) && BW(next.X, X) && board[next.Y][next.X] == 0) return next; return now; } int main(){ while(scanf("%d%d", &X, &Y) && X+Y){ int tx, ty, kx, ky; scanf("%d%d%d%d", &tx, &ty, &kx, &ky); tx--; ty--; kx--; ky--; rep(i, Y) rep(j, X) scanf("%d", &board[i][j]); map<pair<pi,pi>, bool>m; // t k queue<pii>tq, kq; tq.push(make_pair(ty, tx)); kq.push(make_pair(ky, kx)); m[make_pair(make_pair(ty, tx), make_pair(ky, kx))] = 1; int res = 1; while(!tq.empty()){ if(res >= 100) break; int qsize = (int)tq.size(); rep(i, qsize){ pii t = tq.front(); tq.pop(); pii k = kq.front(); kq.pop(); rep(j, 4){ pii nt = nextp(t, j, 1), nk = nextp(k, j, -1); pair<pi, pi> next = make_pair(make_pair(nt.Y, nt.X), make_pair(nk.Y, nk.X)); if(m.count(next) == 1) continue; if(nt == nk){ printf("%d\n", res); goto end; } m[next] = 1; tq.push(nt); kq.push(nk); } } res++; } puts("NA"); end:; } return 0; }
実行時間が0.081s、何歩目かをキューに入れといて、rep(i, qsize)を無くすと 速くなるんかな。