C++で解くUnique Paths II：障害物のあるグリッドでのユニークな経路数を動的計画法で求める

あるロボットが n × m のグリッド（n行・m列）の左上の角に配置されているとします。ロボットは任意の時点で下方向または右方向にしか移動できません。そして、グリッドの右下の角（下図では「END」と表示）を目指して移動します。

ただし、グリッドの中には障害物としてマークされたセルが存在する場合があります。このとき、「スタート地点からゴール地点まで到達できる一意な経路は何通りあるか」を求めるのがこの問題です。

例えば、グリッドが [[0,0,0],[0,1,0],[0,0,0]] である場合、盤面は次のようになります（1が障害物を表します）。

この場合の出力は 2 となります。つまり、スタートからゴールまでたどり着ける経路は全部で2通りあり、具体的には以下の2つです。

1. 右 → 右 → 下 → 下
2. 下 → 下 → 右 → 右

解法のアプローチ（動的計画法）

この問題は動的計画法（DP）を使うことで効率的に解けます。各セルに「そのセルからゴールまで到達できる経路の数」を持たせていくイメージです。手順は以下のとおりです。

• a := 行数、b := 列数 とする
• もし grid[a - 1][b - 1]（ゴール地点）が障害物なら、到達不可能なので 0 を返す
• a × b のサイズのテーブル dp を作成する
• i := b - 1 から 0 まで減少させながら処理：
  • grid[a - 1][i] が障害物なら break、そうでなければ dp[a - 1][i] := 1（最終行は右に進むしかないため）
• i := a - 1 から 0 まで減少させながら処理：
  • grid[i][b - 1] が障害物なら break、そうでなければ dp[i][b - 1] := 1（最終列は下に進むしかないため）
• i := a - 2 から 0 まで、j := b - 2 から 0 まで二重ループ：
  • grid[i][j] が 0（障害物なし）の場合は dp[i][j] := dp[i + 1][j] + dp[i][j + 1]、障害物がある場合は 0
• 最後に dp[0][0] を返す

ポイントは、右端の列と下端の行は移動の選択肢が1通りしかないため、障害物にぶつかるまですべて 1 で初期化できるところです。それより内側のセルは「下のセルからの経路数」と「右のセルからの経路数」の合計になります。

それでは、実際の実装を見て理解を深めましょう。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
      int a = obstacleGrid.size();
      int b = obstacleGrid[0].size();
         if(!a || !b) return 0;
      if(obstacleGrid[a - 1][b - 1])return 0;
      vector < vector <lli> > dp(a, vector <lli>(b));
      for(int i = b - 1; i >= 0; i--)if(obstacleGrid[a-1][i]) break; else dp[a-1][i] = 1;
      for(int i = a - 1; i >= 0; i--)if(obstacleGrid[i][b - 1]) break; else dp[i][b-1] = 1 ;
      for(int i = a-2; i >= 0; i--){
         for(int j = b-2 ; j >= 0; j--)dp[i][j] = !obstacleGrid[i][j]? dp[i+1][j] + dp[i][j+1] : 0;
      }
      return dp[0][0];
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};
   cout << ob.uniquePathsWithObstacles(v);
}

入力

[[0,0,0],[0,1,0],[0,0,0]]

出力

2

計算量について

このアルゴリズムの時間計算量は O(n × m)、空間計算量も O(n × m) となります。グリッドの各セルを一度だけ訪れて値を埋めていくため、全経路を実際に辿るような指数時間の探索に比べて格段に効率的です。さらに工夫すれば、DPテーブルを1行分だけ保持することで空間計算量を O(m) まで削減することも可能です。