Cho một Mê cung được biểu diễn dưới dạng ma trận cột X hàng trong đó chướng ngại vật được biểu thị là -1 và một ô rõ ràng có giá trị khác -1. Mục tiêu là bắt đầu từ arr ô đầu tiên [0] [0] và đến ô cuối cùng arr [row] [col] sao cho chỉ cho phép hai lần di chuyển:
- Di chuyển sang phải arr [i] [j] đến arr [i] [j + 1] và
- Di chuyển xuống arr [i] [j] đến arr [i + 1] [j].
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [row] [col] ={{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}
Đầu ra - Tổng số cách để đến đích trong Mê cung là:1
Giải thích
0 1 2
0 0 0 0
1 -1 -1 0
2 0 0 0
Các cách sẽ là:
- ô (0,0) → ô (0,1) → ô (0,2) → ô (1,2) → ô (2,0)
Đầu vào - arr [row] [col] ={{0, 0, 0, 0}, {-1, 0, -1, 0}, {-1, 0, -1, 0}, {0, 0, 0, 0}}
Đầu ra - Đếm số cách để đến đích trong Mê cung là:2
Giải thích
0 1 2 3
0 0 0 0 0
1 -1 0 -1 0
2 -1 0 -1 0
3 0 0 0 0
Các cách sẽ là:
- ô (0,0) → ô (0,1) → ô (1,1) → ô (2,1) → ô (3,1) → ô (3,2) → ô (3,3 )
- ô (0,0) → ô (0,1) → ô (0,2) → ô (0,3) → ô (1,3) → ô (2,3) → ô (3,3 )
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, trước tiên chúng ta sẽ đặt tất cả các số không thành 1. Duyệt lại ma trận mê cung và bây giờ cho mỗi ô, nếu nó là khối (-1) thì hãy bỏ qua nó. Nếu không, hãy kiểm tra ô trên (i-1, j) và ô bên trái (i, j-1). Nếu nó lớn hơn 0 thì hãy thêm giá trị của nó vào ô hiện tại (i, j). Bằng cách này, chúng ta sẽ nhận được tổng tại ô (hàng-1, cột-1) là tổng số cách để đạt được nó.
- Lấy mảng đầu vào arr [row] [col] làm Mê cung.
- Hàm destination_maze (int arr [row] [col]) nhận arr và trả về số cách để đến đích trong Mê cung.
- Nếu ô đầu tiên bị chặn thì trả về 0 như một cách để đến cuối.
- Bây giờ đi ngang qua cột ngoài cùng bên trái và đặt tất cả các số 0 thành 1. Lúc đầu, sự tắc nghẽn sẽ phá vỡ vòng lặp vì không thể tiếp cận các ô bên dưới nó. Bắt đầu từ chỉ mục i =0 đến i
- Tương tự, làm cho hàng đầu tiên từ j =0 đến j
- Duyệt lại arr từ ô (1,1) và nếu arr [i] [j] là -1 thì không làm gì cả.
- Nếu arr [i-1] [j] hoặc arr [i] [j-1] lớn hơn 0 thì arr [i] [j] có thể truy cập được từ chúng. Vì vậy, hãy thêm giá trị của họ vào đó.
- Cuối cùng, chúng tôi sẽ có arr [row-1] [col-1] là tổng số cách để tiếp cận nó.
- Nếu nó> 0 thì trả về nó, nếu không thì trả về 0.
- Tương tự, làm cho hàng đầu tiên từ j =0 đến j
Ví dụ
#include<bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
int destination_maze(int arr[row][col]) {
if (arr[0][0] == -1) {
return 0;
}
for (int i = 0; i < row; i++) {
if (arr[i][0] == 0) {
arr[i][0] = 1;
} else {
break;
}
}
for (int i = 1; i < col; i++) {
if (arr[0][i] == 0) {
arr[0][i] = 1;
} else {
break;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (arr[i][j] == -1) {
continue;
}
if (arr[i - 1][j] > 0) {
arr[i][j] = (arr[i][j] + arr[i - 1][j]);
}
if (arr[i][j - 1] > 0) {
arr[i][j] = (arr[i][j] + arr[i][j - 1]);
}
}
}
if (arr[row - 1][col - 1] > 0) {
return arr[row - 1][col - 1];
} else {
return 0;
}
}
int main() {
int arr[row][col] = {
{
0,
0,
0
},
{
-1,
-1,
0
},
{
0,
0,
0
}
};
cout << "Count of number of ways to reach destination in a Maze are: " << destination_maze(arr);
return 0;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of number of ways to reach destination in a Maze are: 1