Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Chuột trong mê cung cho phép nhảy nhiều bước (Rat in a Maze with Jumps) bằng C++


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++.