Rat in the maze

Given a NxN matrix with 0s and 1s. A block with value 0 is a dead end, we cannot use this block to move ahead. While a block with value 1 can be used to travel ahead in the matrix. Now, consider mat[0][0] as the starting point for the rat. We have to verify, if there exists a path in the matrix for the rat to reach the end point ie mat[N-1][N-1].

Maze

Also, the rat could only move forward () and down (↓) .

This problem could be solved by Backtracking.

Pseudocode
1. Start from the source node ie maze[0][0]
2. Check if we could move right or down ie if mat[i][j+1] == 1
   or mat[i+1][j] == 1
3. If the path reaches the destination, return true
4. Else backtrack and move to a different path
Code Implementation
//
//  main.cpp
//  Rat in the Maze
//
//  Created by Himanshu on 25/09/21.
//

#include <iostream>
using namespace std;
const int N = 4;

void printPath(int sol[][N]) {
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cout<<sol[i][j]<<" ";
        }
        cout<<endl;
    }
}

bool solve (int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N-1 && y == N-1) {
        sol[x][y] = 1;
        return true;
    }
    
    if (maze[x][y] == 1) {
        sol[x][y] = 1;
        if (solve(maze, x+1, y, sol)) {
            return true;
        }
        if (solve(maze, x, y+1, sol)) {
            return true;
        }
        sol[x][y] = 0;
    }
    return false;
}

int main() {
    int maze[N][N] = {{1, 1, 0, 0},
                     {1, 1, 1, 0},
                     {0, 1, 0, 1},
                     {0, 1, 1, 1}};
    
    int sol[N][N];
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            sol[i][j] = 0;
        }
    }
    
    if (solve(maze, 0, 0, sol)) {
        cout<<"Path exists. Path is marked with 1:"<<endl;
        printPath(sol);
    } else {
        cout<<"Path does not exist";
    }
    return 0;
}

Output

Path exists. Path is marked with 1:
1 0 0 0 
1 1 0 0 
0 1 0 0 
0 1 1 1

Here’s a working example:

https://ideone.com/3iBr2J

One thought on “Rat in the maze

  1. Hi, I do think this is a great blog. I stumbledupon it 😉 I’m going to return yet
    again since i have book-marked it. Money and freedom is the
    best way to change, may you be rich and continue to help other people.

Leave a Reply

Your email address will not be published.