RPG Maker [JAG Practice Contest for ACM-ICPC Asia Regional 2017 F]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_f

縦H,横Wの盤面がある
H = 4n-1, W = 4m-1である

• '@'は始点
• '*'は町
• '#'は道路
• '.'は何もない

始点と町はx,y座標がどちらも偶数番目にある。
現在の盤面は道路が無いので、以下のルールをみたすように道路を作り、一筆書きを考える。

1. 道路を使ってできるだけ多くの町に行けるようにする
2. The journey must consist of distinct non-empty cells in this map.
3. 一筆書きは始点から始める（始点からは道路が1つしか出ない）
4. 一筆書きは任意の町で終える（ある町は道路が1つしか出ない）
5. 一筆書きである必要がある（連結であれ）
6. 分岐があってはいけない（一筆書きなので）
7. 町を通る順番は考慮しない

解法

https://jag2017autumn.contest.atcoder.jp/submissions/1794796

アドホックに解く。
今回は微妙に怪しい条件「始点と町はx,y座標がどちらも偶数番目にある」「H = 4n-1, W = 4m-1である」があるので、最善策がありそうな雰囲気がある。
やってみると公式解説のような図形が出て来る。
これをやるだけ。
　
実装が少し面倒。
自分は3段階に分けて構築した。
　
まず、くねくねを全部書く（base）
公式解説では一部書いていないが、こっちでは全部書く。　
次に、町と始点を反映させる（add）
最後に、始点からdfsをして、始点と町の間の辺を1つ消す（erase）
　
この3手順を確認しながら丁寧に実装していく。

int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int H, W;
string S[50];
string ans[50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];
 
    // base
    rep(y, 0, H) rep(x, 0, W) ans[y] += ".";
    rep(x, 0, W) ans[0][x] = '#';
    rep(y, 0, H) if (y % 2 == 0) rep(x, 0, W) if (x != W / 2) ans[y][x] = '#';
    rep(x, 0, W) ans[H-1][x] = '#';
    rep(y, 0, H) if (y % 2 == 1) {
        if ((y - 1) % 4 == 0) ans[y][0] = ans[y][W - 1] = '#';
        else ans[y][W / 2 - 1] = ans[y][W / 2 + 1] = '#';
    }
 
    // add
    int sx = -1, sy = -1;
    rep(y, 0, H) rep(x, 0, W) {
        if (S[y][x] == '@') sx = x, sy = y, ans[y][x] = '@';
        else if (S[y][x] == '*') ans[y][x] = S[y][x];
    }
 
    // erase
    int x = sx, y = sy;
    while (ans[y][x] != '*') {
        if(ans[y][x] != '@') ans[y][x] = '.';
        int ok = 0;
        rep(i, 0, 4) {
            int xx = x + dx[i], yy = y + dy[i];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) if (ans[yy][xx] == '#') {
                x = xx;
                y = yy;
                ok = 1;
                break;
            }
        }
        if (!ok) break;
    }
 
    rep(y, 0, H) printf("%s\n", ans[y].c_str());
}