The Maze Ii - Leetcode Solution

Problem Statement:

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1:

Input 1: a maze represented by a 2D array

0 0 1 0 0

0 0 0 0 0

0 0 0 1 0

1 1 0 1 1

0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)

Input 3: destination coordinate (rowDest, colDest) = (4, 4)

Output: 12

Explanation: One shortest way is : left -> down -> left -> down -> right -> down -> right. The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Note:

There is only one ball and one destination in the maze.

Both the ball and the destination exist on an empty space, and they will not be at the same position initially.

The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.

The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.

Solution:

Approach:

• The possible directions of the ball are right, down, left and up.
• We will use BFS approach to find shortest distance.
• We will maintain a "visited" matrix of the size of the given matrix, where we mark the already visited positions.
• We will iterate over each direction the ball can move using a for loop. For example, we will first move the ball to its right. And if it can move, we will keep moving it until it stops.
• We will calculate the distance for the current direction and store it in a minDist variable if it is less than the previous distance.
• We will mark the current position as "visited".
• If we reached the destination, we will update the "minDist" variable and keep going in different directions, but for the same distance only because we need to find the shortest distance.
• If the distance of all directions is greater than the previous distance, we return -1 (since we cannot reach the destination).

Code:

class Solution { public: int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) { int n=maze.size(),m=maze[0].size(),i,j,k; vector<vector<int>> v(n,vector<int> (m,0)),d(n,vector<int> (m,INT_MAX)); //v denotes if visisted or not, d denotes distance from source queue<pair<int,int>> q; //source added to the queue q.push(make_pair(start[0],start[1]));
d[start[0]][start[1]]=0; //alternatively we can use v[start[0]][start[1]]=1; , but this is slightly better while(!q.empty()){ //extracting the point in the queue auto x=q.front(); q.pop(); int i=x.first,j=x.second; if(v[i][j]) continue; //if visisted, move forward v[i][j]=1; //marking the point as visisted //Finding minimum distance from the point to the 4 directions :- Right, Left, Up and Down int dist=d[i][j],c=0; for(int k=1;k<=4;k++){ int ii=i,jj=j,step=0; //moving the ball in the selected direction until a wall is encountered if(k==1){ //right while(jj<m-1 and maze[ii][jj+1]==0) jj++,step++; }
else if(k==2){ //left while(jj>0 and maze[ii][jj-1]==0) jj--,step++; } else if(k==3){ //up while(ii>0 and maze[ii-1][jj]==0) ii--,step++; } else{ //down while(ii<n-1 and maze[ii+1][jj]==0) ii++,step++; } //if the destination is reached, return the current minimum distance, as the constraints from question guarantee only one shortest path if(ii==destination[0] and jj==destination[1]) return dist+step; //if the position obtained is less than distance obtained from this position to source, no need of traversing that path again if(d[ii][jj]>dist+step){ d[ii][jj]=dist+step; q.push(make_pair(ii,jj)); } } } //if destination is not reached :( return -1; } };

Time Complexity:

The worst case time-complexity can be obtained if all the cells are visited before reaching the destination. The maximum number of cells that can be visited in such a case is mn. Therefore, the time complexity of the above solution is O(mn+k^2), where k is the maximum length of the queue.

Space Complexity:

A 2D vector d is used to store the distance from the "start" to each position in the maze. Therefore, the space complexity of the above solution is O(m*n).

1