はまやんはまやんはまやん

hamayanhamayan's blog

遭難 [Aizu Competitive Programming Camp 2018 Day 1 D]

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();
}