C++で解く「ユニークパスIII」― DFSとバックトラッキングで全マスを1回だけ通る経路を数える

問題の概要

2次元のグリッドが与えられ、各マスは次の4種類のいずれかで表されます。

• 1 … スタート地点(必ず1つだけ存在します)
• 2 … ゴール地点(必ず1つだけ存在します)
• 0 … 自由に移動できる空きマス
• -1 … 通ることができない障害物

求めるのは、スタートからゴールまで、障害物以外のすべてのマスをちょうど1回ずつ通るような、上下左右4方向への移動による経路の総数です。

入力例

この場合の出力は 2 となります。条件を満たす経路は次の2通りです。

(0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (1,2) → (1,1) → (1,0) → (2,0) → (2,1) → (2,2)
(0,0) → (1,0) → (2,0) → (2,1) → (1,1) → (0,1) → (0,2) → (0,3) → (1,3) → (1,2) → (2,2)

解法のアプローチ:DFS+バックトラッキング

この問題は、深さ優先探索(DFS)とバックトラッキングを組み合わせることで解けます。ポイントは「残りの空きマス数」を管理しながら探索を進め、ゴールに到達した時点ですべてのマスを訪問し終えたかどうかを判定することです。

dfs() 関数の処理内容

dfs() は、グリッド grid、現在位置 (i, j)、ゴール座標 (ex, ey)、残り空きマス数 empty を引数として受け取ります。

• 現在位置がグリッドの範囲外、または grid[i][j] が -1(障害物・訪問済み)の場合は 0 を返します。
• grid[i][j] が 2(ゴール)の場合は、empty が -1(=すべてのマスを訪問済み)であるときに限り true(1)を返します。
• x := 0 として答えを初期化します。
• empty を1減らし、grid[i][j] を -1 にして訪問済みマークを付けます。
• 4方向それぞれについて隣接マス (nx, ny) を計算し、x += dfs(grid, nx, ny, ex, ey, empty) で再帰的に探索します。
• バックトラックとして、empty を1増やし、grid[i][j] を 0 に戻して状態を復元します。
• 最後に x を返します。

uniquePathsIII() の処理内容

• empty := 0 とし、行数 n、列数 m を取得します。
• 全マスを走査し、0 なら empty を増加、1 ならスタート座標 (sx, sy)、2 ならゴール座標 (ex, ey) を記録します。
• dfs(grid, sx, sy, ex, ey, empty) の結果をそのまま返します。

なお、最悪ケースの計算量は O(4^(n×m)) となり、グリッドが小さい前提の問題です。訪問済みマークを一時的に書き込んでから元に戻すことで、追加のメモリをほぼ使わずに実装できる点も特徴です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
    public:
    int dfs(vector<vector<int> >& grid, int i, int j, int ex, int ey,
    int empty){
        if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0
        || grid[i][j] == -1)
        return 0;
        if (grid[i][j] == 2) {
            return empty == -1;
        }
        int x = 0;
        empty--;
        grid[i][j] = -1;
        for (int k = 0; k < 4; k++) {
            int nx = i + dir[k][0];
            int ny = j + dir[k][1];
            x += dfs(grid, nx, ny, ex, ey, empty);
        }
        empty++;
        grid[i][j] = 0;
        return x;
    }
    int uniquePathsIII(vector<vector<int> >& grid){
        int empty = 0;
        int sx, sy, ex, ey;
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0)
                empty++;
                else if (grid[i][j] == 1) {
                    sx = i;
                    sy = j;
                }
                else if (grid[i][j] == 2) {
                    ex = i;
                    ey = j;
                }
            }
        }
        return dfs(grid, sx, sy, ex, ey, empty);
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
    cout << (ob.uniquePathsIII(v));
}

入力

{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}

出力

2