Problem
Given a maze with obstacles, a starting point (top-left), and a destination point (bottom-right), our goal is to find the minimum number of steps the rat needs to take to reach the destination. The maze is represented as a grid where cells can either be open (1) or blocked by obstacles (0).
Also, the rat can only move forward (→) and down (↓).
We’ve already solved the standard Rat in the maze problem here. However, here we’ll be using Breadth First Search (BFS) to find the shortest path in the maze.
Approach
BFS will explore the maze – level by level. Each level corresponds to the number of steps needed to reach that point. Here’s a simple C++ implementation of the BFS algorithm for the Rat in the Maze problem.
Code Implementation
//
// main.cpp
// Rat in the Maze - Min steps
//
// Created by Himanshu on 21/01/24.
//
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 4; // Size of the maze
struct Point {
int x, y, dist;
};
bool isSafe(int maze[N][N], int x, int y, vector<vector<int>>& sol) {
return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1 && sol[x][y] == 0);
}
bool solveMazeBFS(int maze[N][N]) {
vector<vector<int>> sol(N, vector<int>(N, 0));
queue<Point> q;
Point start = {0, 0, 0};
q.push(start);
while (!q.empty()) {
Point current = q.front();
int x = current.x;
int y = current.y;
int dist = current.dist;
q.pop();
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1; // Update solution matrix
cout << "Minimum Steps: " << dist << endl;
return true;
}
if (isSafe(maze, x, y, sol)) {
sol[x][y] = 1;
// Move down
if (isSafe(maze, x + 1, y, sol))
q.push({x + 1, y, dist + 1});
// Move right
if (isSafe(maze, x, y + 1, sol))
q.push({x, y + 1, dist + 1});
}
}
cout << "Solution does not exist" << endl;
return false;
}
int main() {
int maze[N][N] = { {1, 0, 1, 0},
{1, 1, 0, 1},
{0, 1, 1, 1},
{1, 0, 1, 1} };
solveMazeBFS(maze);
return 0;
}
Output
Minimum Steps: 6