AOJ 2861 RPG Maker

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2861

解法

典型構築だと思われる。
4n - 1, 4m - 1 であることが重要で、この制約のためにすべてのマスを回収するようなパスが存在する。
イメージとしては蛇のようにうねうねしながら移動するというもの。

あとは実装を楽にするだけ。とりあえず始点を無視して (0, 0) から始める。
とりあえず (0, 0) -> (h-1, 0) へ一直線に移動する。
その後は蛇のように上に上がっていくと、いずれ (0, 0) にたどり着く。
こうしてできたパスはループになる。
あとは、'@' の位置が始点になるようにパスをずらし (rotate する)、末尾にある余計な移動を削除すればよい。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int h, w; cin >> h >> w;
    vector<string> s(h);
    int sy = -1, sx = -1;
    for(int i = 0; i < h; ++i) {
        cin >> s[i];
        for(int j = 0; j < w; ++j) {
            if(s[i][j] == '@') {
                sy = i, sx = j;
            }
        }
    }

    vector<pii> path;
    for(int i = 0; i < h; ++i) {
        path.emplace_back(i, 0);
    }
    function<void(int, int, int)> snake = [&] (int y, int x, int dx) {
        path.emplace_back(y, x);
        if(x + 2 * dx == 0 && y == 0) {
            path.emplace_back(0, 1);
            return;
        }
        if(x + dx < 2 || w <= x + dx) {
            path.emplace_back(y - 1, x);
            dx *= -1;
            y -= 2;
            snake(y, x, dx);
        } else {
            snake(y, x + dx, dx);
        }
    };
    snake(h - 1, 1, 1);
    rotate(begin(path), find(begin(path), end(path), make_pair(sy, sx)), end(path));
    while(s[path.back().first][path.back().second] != '*') {
        path.pop_back();
    }
    for(auto const& p : path) {
        const int y = p.first, x = p.second;
        if(s[y][x] == '.') {
            s[y][x] = '#';
        }
    }

    for(auto const& t : s) {
        cout << t << endl;
    }
}

感想

焦ると実装が沼になりそう。落ち着いて処理したい。