Cho mê cung biểu diễn bằng ma trận row X col với chướng ngại vật là -1 và ô trống có giá trị khác -1. Mục tiêu: bắt đầu từ ô arr[0][0] đến ô arr[row][col] chỉ cho phép 2 nước đi:
- Sang phải:
arr[i][j]→arr[i][j+1] - Xuống:
arr[i][j]→arr[i+1][j]
Hiểu qua ví dụ
Đầu vào: arr[3][3] = {{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}
Đầu ra: Số cách đến đích: 1
Giải thích: Đường đi: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
Đầu vào: arr[4][4] = {{0,0,0,0}, {-1,0,-1,0}, {-1,0,-1,0}, {0,0,0,0}}
Đầu ra: Số cách đến đích: 2
Giải thích: Hai đường đi: (0,0)→(0,1)→(1,1)→(2,1)→(3,1)→(3,2)→(3,3) và (0,0)→(0,1)→(0,2)→(0,3)→(1,3)→(2,3)→(3,3)
Phương pháp sử dụng
Đặt tất cả 0 thành 1. Duyệt lại ma trận: nếu ô là -1 bỏ qua. Nếu không, kiểm tra ô trên (i-1,j) và ô trái (i,j-1). Nếu > 0 cộng giá trị vào ô hiện tại (i,j). Cuối cùng ô (row-1,col-1) chứa tổng số cách.
- Nhập mảng
arr[row][col]. - Hàm
destination_maze(int arr[row][col])trả về số cách. - Nếu ô đầu bị chặn trả về 0.
- Duyệt cột trái: đặt 0 thành 1, gặp -1 dừng (ô dưới không thể đến).
- Tương tự hàng đầu.
- Duyệt từ ô (1,1): nếu -1 bỏ qua.
- Nếu ô trên hoặc trái > 0 cộng vào ô hiện tại.
- Trả về
arr[row-1][col-1]nếu > 0 else 0.
Ví dụ mã nguồn
#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 - 1][j];
if (arr[i][j - 1] > 0) 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;
}
Chạy mã trên cho kết quả:
Kết quả
Count of number of ways to reach destination in a Maze are: 1