Chuột trong Mê cung với nhiều bước hoặc cho phép nhảy?

Vấn đề con chuột trong mê cung là một trong những vấn đề nổi tiếng của quá trình bẻ khóa ngược. Ở đây chúng ta sẽ thấy vấn đề đó với ít biến thể. Giả sử đã cho một mê cung NxN M. Điểm bắt đầu là góc trên bên trái M [0, 0] và điểm đến là góc dưới bên phải M [N - 1, N - 1]. Một con chuột được đặt ở điểm xuất phát. Mục tiêu của chúng tôi là tìm một con đường từ điểm bắt đầu đến điểm kết thúc mà chuột có thể đi đến đích. Ở đây con chuột có thể nhảy (Các biến thể). Bây giờ có một số ràng buộc

Chuột có thể di chuyển sang phải hoặc hướng xuống.
Mê cung với số 0 trong ô cho biết rằng ô đó đã bị chặn.
Các ô khác 0 cho biết đường dẫn hợp lệ.
Con số bên trong ô cho biết số bước nhảy tối đa mà chuột có thể thực hiện từ ô đó.

Thuật toán

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

Ví dụ

#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) { //check whether x,y is valid or not
   // when (x, y) is outside of the maze, then return false
   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) { //if destination is found, return true
      sol[x][y] = 1;
      return true;
   }
   if (isSafe(maze, x, y)) {
      sol[x][y] = 1; //mark 1 into solution matrix
      for (int i = 1; i <= maze[x][y] && i < N; i++) {
         if (ratMazeSolve(maze, x + i, y, sol)) //move right
            return true;
         if (ratMazeSolve(maze, x, y + i, sol)) //move down
            return true;
      }
      sol[x][y] = 0; //if the solution is not valid, then make it 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;
}
main() {
   int maze[N][N] = { { 2, 1, 0, 0 },
      { 3, 0, 0, 1 },
      { 0, 1, 0, 1 },
      { 0, 0, 0, 1 }
   };
   solveMaze(maze);
}

Đầu ra