C ++で許可されている4つの移動を使用して、左上から右下へのすべてのパスをマトリックスに出力します

この問題では、mXn 2D行列が与えられ、行列の左上から右下までのすべての可能なパスを印刷する必要があります。トラバーサルの場合、左、右、上、下の4方向すべてに移動できます。

右と上への動きはめったに使用されないと思いましたが、これらは時々有益である可能性があります。

トピックをよりよく理解するために例を見てみましょう：

入力：

1 3 5

2 8 9

出力：

1 -> 3 -> 5 -> 9
1 -> 3 -> 8 -> 9
1 -> 2 -> 8 -> 9

この問題を解決するために、あるセルから別のセルに移動し、上下に移動するパスを印刷します。マトリックス内の各セルに対してこれを再帰的に実行します。

再帰的アルゴリズムを実装するプログラムを見てみましょう-

例

#include<iostream>
using namespace std;
void printPathTPtoBR(int *mat, int i, int j, int m, int n, int *path, int pi) {
   if (i == m - 1) {
      for (int k = j; k < n; k++)
         path[pi + k - j] = *((mat + i*n) + k);
      for (int l = 0; l < pi + n - j; l++)
         cout << path[l] << " ";
         cout << endl;
      return;
   }
   if (j == n - 1) {
      for (int k = i; k < m; k++)
         path[pi + k - i] = *((mat + k*n) + j);
      for (int l = 0; l < pi + m - i; l++)
         cout << path[l] << " ";
         cout << endl;
      return;
   }
   path[pi] = *((mat + i*n) + j);
   printPathTPtoBR(mat, i+1, j, m, n, path, pi + 1);
   printPathTPtoBR(mat, i, j+1, m, n, path, pi + 1);
}
void findPath(int *mat, int m, int n) {
   int *path = new int[m+n];
   printPathTPtoBR(mat, 0, 0, m, n, path, 0);
}
int main() {
   int mat[2][3] = {
      {1, 2, 3},
      {4, 5, 6}
   };
   cout<<"Path from top-left to bottom-rigth of matrix are :\n";
   findPath(*mat, 2, 3);
   return 0;
}

出力

Path from top-left to bottom-rigth of matrix are :
1 4 5 6
1 2 5 6
1 2 3 6