Kann eine Maus in einem Labyrinth mehrere Schritte oder Sprünge machen?

Das Maus-im-Labyrinth-Problem ist eines der bekannten Backtracking-Probleme. Hier werden wir sehen, dass das Problem nahezu unverändert bleibt. Angenommen, ein NxN-Labyrinth M sei gegeben. Der Startpunkt ist die obere linke Ecke M[0, 0] und der Endpunkt ist die untere rechte Ecke M[N – 1, N – 1]. Am Startpunkt wird eine Maus platziert. Unser Ziel ist es, einen Weg vom Startpunkt zum Endpunkt zu finden, der es der Maus ermöglicht, ihr Ziel zu erreichen. Hier können Mäuse springen (Variante). Nun gibt es einige Einschränkungen

• Die Maus kann sich nach rechts oder unten bewegen.
• Eine 0 in einer Zelle im Labyrinth bedeutet, dass die Zelle blockiert ist.
• Zellen ungleich Null stellen gültige Pfade dar.
• Die Zahl in einer Zelle gibt die maximale Anzahl an Sprüngen an, die die Ratte von dieser Zelle aus machen kann.
ul>

Algorithmus

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

Beispiel

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

Ausgabe

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

Das obige ist der detaillierte Inhalt vonKann eine Maus in einem Labyrinth mehrere Schritte oder Sprünge machen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!