Snake [第五回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202012-open/tasks/past202012_g

解説

https://atcoder.jp/contests/past202012-open/submissions/22290363

一筆書きを探す問題。
制約がかなり小さいので全探索で一筆書きを探すことができる。
制約の小ささから全探索は思いつくかもしれないが、やり方が問題である。

dfs

dfsで全探索していこう。
dfsする場合は始点をどうするかが問題となる。
この始点も全探索しても間に合うので、こちらも全探索する。

始点から始めてdfsで一筆書きを実施していく。
既に通った所かどうかをvisited配列で管理することで、有効な一筆書きのみを探索するようにする。
枝刈りをがっつり入れたdfsはしっかり早くなるというのが定説なので、dfsで間に合いそうだけど間に合うの？
という場合は有効なものだけをしっかり探索して、他は枝刈りをすることを実践しよう。

int H, W;
string S[4];
int cnt = 0;
//---------------------------------------------------------------------------------------------------
int visited[4][4];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
string dfs(int x, int y, int done = 1) {
    if (done == cnt) {
        return to_string(y + 1) + " " + to_string(x + 1) + "\n";
    }

    visited[y][x] = 1;

    rep(d, 0, 4) {
        int xx = x + dx[d];
        int yy = y + dy[d];

        if (0 <= xx && xx < W && 0 <= yy && yy < H) {
            if (!visited[yy][xx] && S[yy][xx] == '#') {
                auto res = dfs(xx, yy, done + 1);
                if (res != "") {
                    return res + to_string(y + 1) + " " + to_string(x + 1) + "\n";
                }
            }
        }
    }

    visited[y][x] = 0;

    return "";
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '#') cnt++;
    printf("%d\n", cnt);

    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '#') {
        string res = dfs(x, y);
        if (res != "") {
            printf("%s", res.c_str());
            return;
        }
    }
}