In tất cả các đường dẫn từ trên cùng bên trái đến dưới cùng bên phải trong một ma trận với bốn lần di chuyển được phép trong C ++

Trong bài toán này, chúng ta được cung cấp một ma trận 2D mXn và chúng ta phải in tất cả các đường có thể có từ trên cùng bên trái đến dưới cùng bên phải của ma trận. Đối với đường ngang, chúng ta có thể di chuyển theo cả bốn hướng, tức là trái, phải, trên, dưới.

Tưởng rằng các bước di chuyển bên phải và bên trên hiếm khi được sử dụng nhưng đôi khi chúng có thể mang lại lợi ích.

Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề:

Đầu vào:

1 3 5

2 8 9

Đầu ra:

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

Để giải quyết vấn đề này, chúng ta sẽ di chuyển từ ô này sang ô khác và in đường dẫn đi xuống và sang phải. Chúng tôi sẽ thực hiện điều này một cách đệ quy cho từng ô trong ma trận.

Hãy xem một chương trình thực hiện thuật toán đệ quy -

Ví dụ

#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;
}

Đầu ra

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