C++ Rat dans un labyrinthe permettant plusieurs étapes ou sauts

Étant donné un labyrinthe de grille n*n. Notre souris apparaît dans le coin supérieur gauche de la grille. Désormais, la souris ne peut se déplacer que vers le bas ou vers l'avant, et dans cette variante, la souris peut effectuer plusieurs sauts si et seulement si le bloc a désormais une valeur non nulle. Le saut maximum que la souris peut faire à partir de la cellule actuelle est le nombre présent dans la cellule, maintenant votre tâche est de savoir si la souris peut atteindre le coin inférieur droit de la grille, par exemple -

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

Trouvez la solution

ici Dans cette approche, nous utiliserons le retour en arrière pour garder une trace de chaque chemin que la souris peut emprunter maintenant. Si la souris atteint sa destination depuis n'importe quel chemin, nous renvoyons true pour ce chemin, puis imprimons ce chemin. Sinon, on affiche que le chemin n'existe pas.

Exemple

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

Sortie

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

Explication du code ci-dessus

Dans la méthode ci-dessus, nous vérifions chaque chemin qu'il peut générer à partir de la cellule actuelle, lors de la vérification, nous marquons maintenant le chemin comme tel. Lorsque notre chemin atteint une impasse, nous vérifions si l’impasse est notre destination. Maintenant, si ce n'est pas notre destination, nous revenons en arrière, et lorsque nous revenons en arrière, nous marquons la cellule comme 0 car le chemin n'est pas valide, et c'est ainsi que notre code le gère.

Conclusion

Dans ce tutoriel, nous allons résoudre le problème de la souris dans un labyrinthe, permettant plusieurs étapes ou sauts. Nous avons également appris le programme C++ pour ce problème et la méthode complète (générique) pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!