Mê cung N×N, chuột bắt đầu (0,0) đích (N-1,N-1). Ô giá trị k cho phép nhảy tối đa k bước sang phải hoặc xuống. Tìm đường đi (đánh dấu 1) hoặc báo không có đường.
Cách tiếp cận: Backtracking
Đệ quy thử mọi nhảy từ 1 đến maze[x][y] theo 2 hướng (phải, xuống). Đánh dấu đường đi trong mảng sol. Nếu đến đích → true. Nếu hết đường → backtrack (gán 0).
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define N 4
bool solveMaze(int maze[N][N], int x, int y, int sol[N][N]) {
if (x == N-1 && y == N-1) { sol[x][y] = 1; return true; }
if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
sol[x][y] = 1;
for (int i = 1; i <= maze[x][y] && i < N; i++) {
if (solveMaze(maze, x + i, y, sol)) return true; // nhảy xuống
if (solveMaze(maze, x, y + i, sol)) return true; // nhảy phải
}
sol[x][y] = 0; return false;
}
return false;
}
int main() {
int maze[N][N] = { {2,1,0,0}, {3,0,0,1}, {0,1,0,1}, {0,0,0,1} };
int sol[N][N]; memset(sol, 0, sizeof(sol));
if (solveMaze(maze, 0, 0, sol)) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) cout << sol[i][j] << " ";
cout << "\n";
}
} else cout << "Path doesn't exist\n";
return 0;
}
Kết quả
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
Kết luận
Giải mê cung cho phép nhảy nhiều bước bằng backtracking. Code C++.