https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day1/problems/D
解説
https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day1/3148892
右手法を使って解く。
外周に沿って右手法で移動すれば、
- 必ず一周して戻ってくる
- 同じ形であれば、同じルートになる（違う形ならば、違うルートになる）
ということが言える。
record関数を使ったあと、search関数を使って答えを導こう。
record関数
まずは、質問をして、同じ所まで戻ってくるように右手法を適用していこう。
移動の履歴はすべてhistory配列で保存しておく。状態を(x座標, y座標, 向き)とかくことにする。
最初に、外周に行くために、壁に到達するまで左に移動しておこう。
次に、最初の状態を(1010, 1010, 1)として、右手法で移動していこう。
通ったことのある状態に移動したら（一周したら）、終了。
終了時の座標をlastx, lastyとして保存しておこう。
ここですべての状態のx座標の最小をmix, y座標の最小をmiyとしたときに、
この座標が(0,0)になるように座標をすべて移す（終了時の座標も）。
具体的にはx-mix, y-miyで変換する。
これをソートして重複する座標を除いたものをmovとする。
このmovは何かと言うと、今いる島をハッシュ化したものと言える。
※ 島のハッシュ化
ある島を特定するために、(mix, miy)を(0,0)とした島の座標をソートしたものを使う。
同じ形の島であれば、このソート列は等しくなる。
つまりハッシュとして使える。
search関数
すべての島についてハッシュを計算して、同じものが無いか探す。
同じものがあれば、lastx += mix, lasty += miyとして、最後の状態を実際の座標に直す。
あとは、一番最初の座標に戻すために、historyを逆順に使って、移動をさかのぼっていこう。
string dir[4] = { "L","D", "R", "U" }; int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 } ; int H, W; string B[505]; vector<int> history; //--------------------------------------------------------------------------------------------------- int check(int x, int y, int d) { int xx = x + dx[d]; int yy = y + dy[d]; if (xx < 0 or W <= xx or yy < 0 or H <= yy) return 0; if (B[yy][xx] == '.') return 0; return 1; } //--------------------------------------------------------------------------------------------------- int cux = 3, cuy = 1; int dbg = 0; int ask(int com) { printf("? %s\n", dir[com].c_str()); fflush(stdout); if (dbg) { int xx = cux + dx[com]; int yy = cuy + dy[com]; if (xx < 0 or W <= xx or yy < 0 or H <= yy) return 0; if (B[yy][xx] == '.') return 0; cux = xx; cuy = yy; return 1; } string res; cin >> res; if (res == "NO") return 0; return 1; } //--------------------------------------------------------------------------------------------------- int vis[2010][2010][4]; vector<pair<int, int>> mov; int lastx, lasty; void record() { while(ask(0)) history.push_back(0); vector<pair<int, int>> tmp; int x = 1010, y = 1010, d = 1; int mix = 1010, miy = 1010; while (vis[y][x][d] == 0) { vis[y][x][d] = 1; tmp.push_back({ x, y }); chmin(mix, x); chmin(miy, y); rep(dd, 0, 4) { int d2 = (d + 3 + dd) % 4; int res = ask(d2); if (res) { history.push_back(d2); x += dx[d2]; y += dy[d2]; d = d2; break; } } } lastx = x - mix; lasty = y - miy; fore(p, tmp) mov.push_back({ p.first - mix, p.second - miy }); sort(all(mov)); mov.erase(unique(all(mov)), mov.end()); } //--------------------------------------------------------------------------------------------------- int done[501][501][4], used[501][501]; void search() { rep(sy, 0, H) rep(sx, 0, W) if (B[sy][sx] == '#') { if (done[sy][sx][0] or done[sy][sx][1] or done[sy][sx][2] or done[sy][sx][3]) continue; if (B[sy - 1][sx] == '#') continue; if (B[sy][sx - 1] == '#') continue; vector<pair<int, int>> mov2; int x = sx, y = sy, d = 0; int mix = sx, miy = sy; while (done[y][x][d] == 0) { done[y][x][d] = 1; if (!used[y][x]) { mov2.push_back({ x, y }); used[y][x] = 1; } chmin(mix, x); chmin(miy, y); rep(dd, 0, 4) { int d2 = (d + 3 + dd) % 4; int res = check(x, y, d2); if (res) { x += dx[d2]; y += dy[d2]; d = d2; break; } } } fore(p, mov2) p.first -= mix, p.second -= miy; sort(all(mov2)); if (mov.size() != mov2.size()) continue; int n = mov.size(); int ok = 1; rep(i, 0, n) if (mov[i] != mov2[i]) ok = 0; if (ok) { int x = lastx + mix; int y = lasty + miy; reverse(all(history)); fore(com, history) { x += dx[(com + 2) % 4]; y += dy[(com + 2) % 4]; } printf("! %d %d\n", y, x); return; } } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W; rep(y, 0, H) cin >> B[y]; record(); search(); }
