C++ Rat in maze allowing multiple steps or jumps

Given an n*n grid maze. Our mouse appears in the upper left corner of the grid. Now the mouse can only move down or forward, and in this variant the mouse can make multiple jumps if and only if the block now has a non-zero value. The maximum jump that the mouse can make from the current cell is the number present in the cell, now your task is to find out if the mouse can reach the bottom right corner of the grid, for example -

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

Ways to find the solution

In this approach we will use backtracking to keep track of every path the mouse can take now. If the mouse reaches its destination from any path, we return true for that path and then print that path. Otherwise, we print that the path does not exist.

Example

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

Output

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

Explanation of the above code

In the above method, we check every path it can generate from the current cell , when inspecting, we now mark the path as one. When our path reaches a dead end, we check if the dead end is our destination. Now, if that's not our destination, we backtrack, and when we backtrack, we mark the cell as 0 because that path is invalid, and that's how our code handles it.

Conclusion

In this tutorial we will solve a mouse problem in a maze, allowing for multiple steps or jumps. We also learned the C program for this problem and the complete method (general) to solve it. We can write the same program in other languages ​​such as C, java, python and other languages. We hope you found this tutorial helpful.

The above is the detailed content of C++ Rat in maze allowing multiple steps or jumps. For more information, please follow other related articles on the PHP Chinese website!