# Rat in the maze

Given an 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 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].

Also, the rat could only move forward (→) and down (↓) .
This problem can be solved by Backtracking.

###### Pseudocode
1. Start from the source node ie maze
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 (x >= 0 && x < N && y >= 0 && y < N && 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: Rat in the maze

### 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.