ปัญหาหนูในเขาวงกต อนุญาตให้กระโดดหลายขั้น

ปัญหาหนูในเขาวงกตเป็นปัญหา Backtracking ที่ 유명한 นี่คือรูปแบบที่ปรับเปลี่ยนเล็กน้อย สมมติมีเขาวงกต NxN เริ่มที่มุมซ้ายบน M[0,0] จบที่มุมขวาล่าง M[N-1, N-1] หนูสามารถเคลื่อนที่ไปขวาหรือลงได้ เซลล์ที่เป็น 0 คือทางตstructed เซลล์ที่ไม่ใช่ 0 คือทางเดิน ตัวเลขในเซลล์บอกจำนวนขั้นสูงสุดที่หนูสามารถกระโดดได้จากเซลล์นั้น

อัลกอริทึม

ratInMaze

begin
    if destination is reached then
        print the solution matrix
    else
        1. Place the current cell inside the solution matrix as 1
        2. Move forward or jump (check max jump value) and recursively check if move leads to solution or not.
        3. If the move taken from the step 2 is not correct, then move down, and check it leads to the solution or not
        4. If none of the solutions in step 2 and 3 are correct, then make the current cell 0.
    end if
end

ตัวอย่างโค้ด (C++)

#include <iostream>
#define N 4
using namespace std;

void dispSolution(int sol[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << sol[i][j] << " ";
        cout << endl;
    }
}

bool isSafe(int maze[N][N], int x, int y) {
    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0)
        return true;
    return false;
}

bool ratMazeSolve(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 (isSafe(maze, x, y)) {
        sol[x][y] = 1;
        for (int i = 1; i <= maze[x][y] && i < N; i++) {
            if (ratMazeSolve(maze, x + i, y, sol)) return true; // ขวา
            if (ratMazeSolve(maze, x, y + i, sol)) return true; // ลง
        }
        sol[x][y] = 0;
        return false;
    }
    return false;
}

bool solveMaze(int maze[N][N]) {
    int sol[N][N] = { {0,0,0,0}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0} };
    if (!ratMazeSolve(maze, 0, 0, sol)) {
        cout << "Solution doesn't exist";
        return false;
    }
    dispSolution(sol);
    return true;
}

int main() {
    int maze[N][N] = { {2,1,0,0}, {3,0,0,1}, {0,1,0,1}, {0,0,0,1} };
    solveMaze(maze);
}

ผลลัพธ์

1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1