【典型90問】072 - Loop Railway Plan（★4）

問題へのリンク

解法

最短経路を求めたりする問題ではないので、BFSではなくDFSがしたい気分になる。
制約がとても緩いので、全探索が有効そう。
スタート地点は最大でも16通りしかないので、すべてのスタート地点から探索を開始してみることにする。
DFSの関数内では、前後左右にまだ見ていない場所へ移動し、スタート地点に帰ってきたらその時点の移動回数でMaxを取ることにする。

実装

引数が大変なことになってしまった。このあたりを綺麗にすばやく実装できるようになりたい。
制約が緩かったので、この実装でもMLEにならずにすんだ。DFSするときに配列などを値渡しにするとメモリを食うので、制約がきつい時はこういうことはできない。

int H, W;
vector<vector<int>> direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void dfs(int y, int x, vector<vector<bool>> seen, int gy, int gx, int cnt, vector<string> &C, int &ans) {
    seen[y][x] = true;

    // 前後左右に移動
    REP (i, 4) {
        int ny = y + direction[i][0];
        int nx = x + direction[i][1];

        if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;

        if (ny == gy && nx == gx) {
            if (cnt >= 3) chmax(ans, cnt);
            return;
        }

        if (C[ny][nx] == '.' && !seen[ny][nx]) {
            dfs(ny, nx, seen, gy, gx, cnt+1, C, ans);
        }
    }
}

int main(){
    cin >> H >> W;
    vector<string> C(H);
    REP (i, H) cin >> C[i];

    int ans = 0;
    REP (y, H) {
        REP (x, W) {
            if (C[y][x] == '#') continue;

            vector<vector<bool>> seen(H, vector<bool>(W, false));
            dfs(y, x, seen, y, x, 1, C, ans);
        }
    }

    c((ans == 0 ? -1 : ans))
    
    return 0;
}

模範解答のコード例を考察する

下のコードはGitHubで公開されている実装例です。 リンク
自分の実装があまりに汚いので、上手い再帰の書き方を学ぼうと思います。

int H, W;
char c[20][20];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
bool used[20][20];

int dfs(int sx, int sy, int px, int py) {
    if (sx == px && sy == py && used[px][py] == true) return 0;
    used[px][py] = true;

    int ret = -10000;
    for (int i = 0; i < 4; i++) {
        int nx = px + dx[i], ny = py + dy[i];
        if (nx < 1 || ny < 1 || nx > H || ny > W || c[nx][ny] == '#') continue;
        if ((sx != nx || sy != ny) && used[nx][ny] == true) continue;
        int v = dfs(sx, sy, nx, ny);
        ret = max(ret, v + 1);

    }
    used[px][py] = false;
    return ret;
}

この実装では、これまでにどのマスを見てきたかをそれぞれの経路ごとに保持していない。
行きがけにusedをtrueにし、帰りがけにfalseに戻すことによって管理しているようだ。

また、現在何回移動を繰り返したかを管理していないようだ。
スタート地点に帰って来れた場合、0を返し、帰りがけに移動回数のカウントを増やしていっているようだ。
retはゴールしてから、その地点までどれだけ大回りしてその地点に戻ることができたかを保持している。
最終的に最大移動回数を戻り値として返すことになる。