C++で迷路内の目的地に到達する経路の数を数える方法

問題の概要

迷路は行 × 列(row × col)の行列として表現され、障害物のあるセルは -1、通行可能なセルには -1 以外の値が格納されています。ゴールは、左上のセル arr[0][0] から出発し、右下のセル arr[row-1][col-1] に到達することです。ただし、許される移動は次の2方向のみです。

• 右への移動: arr[i][j] → arr[i][j+1]
• 下への移動: arr[i][j] → arr[i+1][j]

例で理解しよう

入力 − arr[row][col] = {{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}

出力 − 迷路で目的地に到達する方法の数: 1

説明:

       0    1    2
  0    0    0    0
  1   -1   -1    0
  2    0    0    0

到達できる経路は次の1通りだけです。

• (0,0) → (0,1) → (0,2) → (1,2) → (2,2)

入力 − arr[row][col] = {{0, 0, 0, 0}, {-1, 0, -1, 0}, {-1, 0, -1, 0}, {0, 0, 0, 0}}

出力 − 迷路で目的地に到達する方法の数: 2

説明:

       0    1    2    3
  0    0    0    0    0
  1   -1    0   -1    0
  2   -1    0   -1    0
  3    0    0    0    0

到達できる経路は次の2通りです。

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

アルゴリズムの考え方

このアプローチでは、まずすべての 0 を 1 に置き換えます。これは「そのセルへは少なくとも1つの経路で到達できる」ことを意味します。続いて、迷路の行列をもう一度走査し、各セルに対して次のように処理を行います。セルが障害物(-1)であれば無視してスキップし、そうでなければ上のセル (i-1, j) と左のセル (i, j-1) の値を調べます。これらの値が 0 より大きければ(= そこから到達可能であれば)、その値を現在のセル (i, j) に加算します。この操作を繰り返すことで、セル (row-1, col-1) に目的地までの総経路数が蓄積されていきます。

処理の手順

1. 入力配列 arr[row][col] を迷路として受け取ります。
2. 関数 destination_maze(int arr[row][col]) は、迷路で目的地に到達する方法の数を返します。
3. 出発点のセルが障害物(-1)で塞がれている場合は、0 を返します。
4. 最左列を上から順に走査し、値が 0 のセルを 1 に置き換えます。障害物にぶつかった時点でループを中断します(それより下のセルには到達できないため)。
5. 同様に、最上行も左から順に走査し、値が 0 のセルを 1 に置き換えます。
6. セル (1,1) から配列全体を再び走査します。arr[i][j] が -1 なら何もせずスキップします。
7. arr[i-1][j](上のセル)または arr[i][j-1](左のセル)が 0 より大きければ、そこから現在のセルへ到達できるため、その値を加算します。
8. 最終的に arr[row-1][col-1] の値が、目的地に到達する総経路数となります。
9. その値が 0 より大きければそれを返し、そうでなければ 0 を返します。

サンプルコード

#include<bits/stdc++.h>

using namespace std;
#define row 3
#define col 3

int destination_maze(int arr[row][col]) {
    if (arr[0][0] == -1) {
        return 0;
    }
    for (int i = 0; i < row; i++) {
        if (arr[i][0] == 0) {
            arr[i][0] = 1;
        } else {
            break;
        }
    }
    for (int i = 1; i < col; i++) {
        if (arr[0][i] == 0) {
            arr[0][i] = 1;
        } else {
            break;
        }
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (arr[i][j] == -1) {
                continue;
            }
            if (arr[i - 1][j] > 0) {
                arr[i][j] = (arr[i][j] + arr[i - 1][j]);
            }
            if (arr[i][j - 1] > 0) {
                arr[i][j] = (arr[i][j] + arr[i][j - 1]);
            }
        }
    }
    if (arr[row - 1][col - 1] > 0) {
        return arr[row - 1][col - 1];
    } else {
        return 0;
    }
}
int main() {
    int arr[row][col] = {
        {0, 0, 0},
        {-1, -1, 0},
        {0, 0, 0}
    };
    cout << "迷路で目的地に到達する方法の数: " << destination_maze(arr);
    return 0;
}

上記のコードを実行すると、次のような出力が得られます。

出力

迷路で目的地に到達する方法の数: 1

計算量について

このアルゴリズムは、迷路の全セルを高々2回走査するだけで済むため、時間計算量は O(row × col) となります。また、追加の配列を使わず入力配列自体を結果の保存に利用しているため、空間計算量も O(1)(入力を除く)と非常に効率的です。