หนูอยู่ในเขาวงกตที่มีหลายขั้นตอนหรือกระโดดได้รับอนุญาต?

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

• หนูสามารถเคลื่อนที่ไปทางขวาหรือทางด้านล่างได้
• เขาวงกตที่มี 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

ตัวอย่าง

#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);
}

ผลลัพธ์

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