C++でm×n行列の左上から右下への全経路数を求める方法

はじめに

このチュートリアルでは、m×n行列（グリッド）の左上から右下まで移動する際の、取り得るすべての経路の総数を求めるC++プログラムについて解説します。

m×nの行列が与えられたとき、左上のセルから右下のセルへ到達するすべての移動経路を数えることが課題です。なお、移動は「右」または「下」のいずれかの方向のみ許されるものとします。

アルゴリズムの考え方

この問題は再帰を使ってシンプルに解くことができます。セル(m, n)に到達する経路の数は、「上隣のセル(m-1, n)に到達する経路の数」と「左隣のセル(m, n-1)に到達する経路の数」の合計になります。最上行または最左列にあるセルには、それぞれ1通りのみで到達できるため、その場合は1を返します。

コード例

#include <iostream>
using namespace std;
// 可能な経路の数を返す関数
int count_paths(int m, int n){
   if (m == 1 || n == 1)
      return 1;
   return count_paths(m - 1, n) + count_paths(m, n - 1);
}
int main(){
   cout << count_paths(3, 3);
   return 0;
}

出力結果

6

解説

上記のコードでは、count_paths(3, 3) を呼び出しています。3×3の行列の場合、左上から右下までの経路は全部で6通り存在します。この再帰的なアプローチは直感的で理解しやすい反面、同じ計算を何度も繰り返すため非効率になることがあります。大きな行列を扱う場合は、動的計画法（DP）や組み合わせの公式 C(m+n-2, m-1) を利用することで、計算量を大幅に削減できます。