C++で2次元マトリックスの経路の有無を確認する方法

ここでは、0と1で構成された2次元配列（マトリックス）が与えられ、左上の角から右下の角まで到達できる経路が存在するかどうかを判定する問題を扱います。0は通行可能な領域を、1は障害物（ブロック）を表します。なお、左上のセルは常に出発点として扱われるものとします。

例として、次のようなマトリックスを考えてみましょう。

このマトリックスには複数の経路が存在するため、プログラムはtrueを返します。経路が1つも存在しない場合はfalseを返します。

アルゴリズムの考え方

この問題は、到達可能なセルの値をすべて-1に書き換えていくことで解決できます。具体的な手順は以下のとおりです。

• まず、出発点であるarr[0][0]の値を-1に変更します。
• 1行目については、左隣のセルと比較し、現在のセルが障害物（1）でなければ、前のセルの値をそのまま引き継ぎます。
• 1列目についても同様に、上のセルと比較しながら値を伝播させます。
• 続いて、(1,1)から右下に向かって走査し、上のセルと左のセルの値のうち小さい方をmin()で取得します。現在のセルが障害物でない場合は、その最小値を代入します。セルが1の場合は何も変更しません。
• 最後に、右下のセルの値が-1になっていればtrueを、そうでなければfalseを返します。

サンプルコード

#include <iostream>
#define row 5
#define col 5
using namespace std;
bool isPathPresent(int arr[row][col]) {
   arr[0][0] = -1;
   for (int i = 1; i < row; i++)
      if (arr[i][0] != 1)
         arr[i][0] = arr[i - 1][0];
   for (int j = 1; j < col; j++)
      if (arr[0][j] != 1)
         arr[0][j] = arr[0][j - 1];
   for (int i = 1; i < row; i++)
      for (int j = 1; j < col; j++)
         if (arr[i][j] != 1)
            arr[i][j] = min(arr[i][j - 1], arr[i - 1][j]);
   return (arr[row - 1][col - 1] == -1);
}
int main() {
   int arr[row][col] = {{ 0, 0, 0, 1, 0},
      {1, 0, 0, 1, 1},
      { 0, 0, 0, 1, 0},
      {1, 0, 0, 0, 0},
      { 0, 0, 1, 0, 0}};
   if (isPathPresent(arr))
      cout << "Path is present";
   else
      cout << "No path has found";
}

出力

Path is present

計算量について

このアルゴリズムはマトリックス全体を一度だけ走査するため、時間計算量はO(row × col)です。また、入力マトリックス自体を書き換えて利用するため、追加のメモリをほとんど必要とせず、空間計算量はO(1)で実現できます。