打印矩阵中从左上到右下的所有路径,C ++允许四步移动

在这个问题中,我们得到一个mXn 2D矩阵,我们必须打印出矩阵左上角到右下角的所有可能路径。对于遍历,我们可以在所有四个方向上移动,即左,右,上,下。

以为左右移动很少使用,但有时会很有用。

让我们举个例子来更好地理解这个话题:

输入:

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

以上是 打印矩阵中从左上到右下的所有路径,C ++允许四步移动 的全部内容, 来源链接: utcz.com/z/335002.html

回到顶部