ในปัญหานี้ เราได้รับเมทริกซ์ mXn 2D และเราต้องพิมพ์เส้นทางที่เป็นไปได้ทั้งหมดจากด้านบนซ้ายไปด้านล่างขวาของเมทริกซ์ สำหรับการข้ามผ่าน เราสามารถเคลื่อนที่ไปทางขวาและลงในเมทริกซ์เท่านั้น
มาดูตัวอย่างเพื่อทำความเข้าใจหัวข้อกันดีกว่า −
Input: 1 3 5 2 8 9 Output: 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;
} ผลลัพธ์
เส้นทางจากบนซ้ายไปล่างขวาของเมทริกซ์คือ −
1 4 5 6 1 2 5 6 1 2 3 6
