Given an NxN matrix with 0s and 1s. A block with a value of 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, mat[0][0] is the starting point for the rat. We have to verify, if there exists a path in the matrix for the rat to reach the endpoint ie. mat[N-1][N-1].
Also, the rat can only move forward (→) and down (↓).
This problem can 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 (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”
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.