Rat In A Maze Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/rat-in-maze

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a maze in the form of a matrix of size n * m. Each cell is either clear or blocked denoted by 1 and 0 respectively.
A rat sits at the top-left cell and there exists a block of cheese at the bottom-right cell. Both these cells are guaranteed to be clear.
You need to find if the rat can get the cheese if it can move only in one of the two directions - down and right. It can’t move to blocked cells.

Naive Approach

From each cell, we can move either right or down. In the naive approach, we can recursively try to move the right or down from the current cell if it is a valid move until we manage to reach the destination. If even after covering all possible choices we cannot reach the cheese, we conclude that it is impossible to reach the destination cell.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(n * m)

Optimal Approach

In the optimal approach, we use a DFS on grid type algorithm, where we try to move from the current to the possible cells. If we have already reached the current cell, we mark it as visited, and don't recurse from it again. Observe that if the destination cell is possible to reach, then it will be in the same connected component as the starting cell. So after the DFS function is completed, if the destination is visited, then we return true, else false.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Implementation

C++

void getCheese(vector<vector<int>> &maze, vector<vector<int>> &visited, int x, int y) {
	if(x < 0 || y < 0 || x >= maze.size() || y >= maze[0].size()) {
		return;
	}
	if(maze[x][y] == 0) {
		return;
	}
	if(visited[x][y]) {
		return;
	}
	visited[x][y] = true;
	getCheese(maze, visited, x + 1, y);
	getCheese(maze, visited, x, y + 1);
}
bool canGetCheese(vector<vector<int> > &maze) {
    vector<vector<int>> visited(maze.size(), vector<int> (maze[0].size(), 0));
	getCheese(maze, visited, 0, 0);
	if(visited[maze.size() - 1][maze[0].size() - 1]) {
		return true;
	}
	else {
		return false;
	}
}

Java

class Solution {
	void getCheese(int[][] maze, boolean[][] visited, int x, int y) {
		if(x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) {
			return;
		}
		if(maze[x][y] == 0) {
			return;
		}
		if(visited[x][y]) {
			return;
		}
		visited[x][y] = true;
		getCheese(maze, visited, x + 1, y);
		getCheese(maze, visited, x, y + 1);
	}
	boolean canGetCheese(int[][] maze) {
	   	boolean visited[][] = new boolean[maze.length][maze[0].length];
		getCheese(maze, visited, 0, 0);
		if(visited[maze.length - 1][maze[0].length - 1]) {
			return true;
		}
		else {
			return false;
		}
	}
}