C++-Ratte im Labyrinth, die mehrere Schritte oder Sprünge ermöglicht

Gegeben sei ein n*n-Gitterlabyrinth. Unsere Maus erscheint in der oberen linken Ecke des Rasters. Jetzt kann sich die Maus nur noch nach unten oder vorwärts bewegen, und in dieser Variante kann die Maus genau dann mehrere Sprünge machen, wenn der Block jetzt einen Wert ungleich Null hat. Der maximale Sprung, den die Maus von der aktuellen Zelle aus machen kann, ist die in der Zelle vorhandene Zahl. Jetzt müssen Sie herausfinden, ob die Maus beispielsweise die untere rechte Ecke des Rasters erreichen kann -

Input : { { {1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}
},
Output : { {1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}
}

Input : {
{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}
}
Output: Path doesn't exist

Finden Sie die Lösung

hier Bei diesem Ansatz verwenden wir Backtracking, um jeden Weg zu verfolgen, den die Maus jetzt nehmen kann. Wenn die Maus über einen beliebigen Pfad ihr Ziel erreicht, geben wir für diesen Pfad „true“ zurück und geben diesen Pfad dann aus. Andernfalls geben wir aus, dass der Pfad nicht existiert.

Beispiel

 
#include <bits/stdc++.h>
using namespace std;
#define N 4 // size of our grid
bool solveMaze(int maze[N][N], int x, int y, // recursive function for finding the path
    int sol[N][N]){
        if (x == N - 1 && y == N - 1) { // if we reached our goal we return true and mark our goal as 1
            sol[x][y] = 1;
            return true;
    }
    if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
        sol[x][y] = 1; // we include this index as a path
        for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take                                             //so we check for every jump in every direction
            if (solveMaze(maze, x + i, y, sol) == true) // jumping right
               return true;
            if (solveMaze(maze, x, y + i, sol) == true) // jumping downward
               return true;
        }
        sol[x][y] = 0; // if none are true then the path doesn&#39;t exist
                   //or the path doesn&#39;t contain current cell in it
        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&#39;t exist\n";
    return 0;
}

Ausgabe

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

Erklärung des obigen Codes

In der obigen Methode prüfen wir jeden Pfad, der aus der aktuellen Zelle generiert werden kann. Während der Überprüfung markieren wir den Pfad nun als einen. Wenn unser Weg in eine Sackgasse gerät, prüfen wir, ob die Sackgasse unser Ziel ist. Wenn das nicht unser Ziel ist, gehen wir zurück, und wenn wir zurückgehen, markieren wir die Zelle als 0, weil der Pfad ungültig ist, und so geht unser Code damit um.

Fazit

In diesem Tutorial lösen wir das Mausproblem in einem Labyrinth, das mehrere Schritte oder Sprünge ermöglicht. Wir haben auch das C++-Programm für dieses Problem und die vollständige (generische) Methode zur Lösung gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonC++-Ratte im Labyrinth, die mehrere Schritte oder Sprünge ermöglicht. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!