# Rat in the maze | Minimum number of steps

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