Hãy xem xét chúng ta có một mảng 2D. Chúng ta phải tìm xem liệu chúng ta có thể có được một con đường từ góc trên bên trái đến góc dưới cùng bên phải hay không. Ma trận được điền bằng 0 và 1s. 0 cho biết khu vực mở, 1 cho biết tắc nghẽn. Lưu ý rằng góc trên cùng bên trái sẽ luôn là 1.
Giả sử một ma trận giống như dưới đây -
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
Một con đường được đánh dấu là màu xanh lá cây, cũng có một số con đường khác. Vì vậy, chương trình sẽ trả về true, nếu có một đường dẫn, ngược lại là false.
Chúng tôi sẽ giải quyết vấn đề này, bằng cách thay đổi tất cả các nút có thể truy cập thành -1, Đầu tiên thay đổi giá trị của điểm bắt đầu thành -1, sau đó lấy giá trị tiếp theo trong hàng đầu tiên và so sánh với giá trị trước đó, đặt giá trị hiện tại bằng giá trị trước đó iff nó có thể truy cập được (không phải 0). Cũng làm tương tự cho các giá trị cột. Bằng cách so sánh và thiết lập dòng điện với các giá trị cột trước đó nếu có thể truy cập được. Sau đó, bắt đầu từ hàng đầu tiên, cột đầu tiên và lấy các giá trị của hàng trước đó, cột trước đó, lấy giá trị tối thiểu giữa chúng. Và đặt chỉ số hiện tại ở mức tối thiểu. Nếu chỉ số hiện tại là 1, thì không có gì thay đổi. Ở cuối nếu chỉ mục cuối cùng giống với phía dưới bên phải, thì trả về true, ngược lại là false.
Ví dụ
#include <iostream>
#define row 5
#define col 5
using namespace std;
bool isPathPresent(int arr[row][col]) {
arr[0][0] = -1;
for (int i = 1; i < row; i++)
if (arr[i][0] != 1)
arr[i][0] = arr[i - 1][0];
for (int j = 1; j < col; j++)
if (arr[0][j] != 1)
arr[0][j] = arr[0][j - 1];
for (int i = 1; i < row; i++)
for (int j = 1; j < col; j++)
if (arr[i][j] != 1)
arr[i][j] = min(arr[i][j - 1], arr[i - 1][j]);
return (arr[row - 1][col - 1] == -1);
}
int main() {
int arr[row][col] = {{ 0, 0, 0, 1, 0},
{1, 0, 0, 1, 1},
{ 0, 0, 0, 1, 0},
{1, 0, 0, 0, 0},
{ 0, 0, 1, 0, 0}};
if (isPathPresent(arr))
cout << "Path is present";
else
cout << "No path has found";
} Đầu ra
Path is present