Problem

You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.

Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.

Examples

Example 1: $$ board = \begin{bmatrix} \colorbox{green} f & \colorbox{green} f & \colorbox{green} f & \colorbox{green} f \\ \colorbox{red} t & \colorbox{red} t & \colorbox{green} f & \colorbox{red} t \\ \colorbox{green} f & \colorbox{green} f & \colorbox{green} f & \colorbox{green} f \\ \colorbox{green} f & \colorbox{green} f & \colorbox{green} f & \colorbox{green} f \end{bmatrix} \Longrightarrow path = \begin{bmatrix} \colorbox{blue} f & \colorbox{blue} f & \colorbox{blue} f & \colorbox{green} f \\ \colorbox{red} t & \colorbox{red} t & \colorbox{blue} f & \colorbox{red} t \\ \colorbox{blue} f & \colorbox{blue} f & \colorbox{blue} f & \colorbox{green} f \\ \colorbox{blue} f & \colorbox{green} f & \colorbox{green} f & \colorbox{green} f \end{bmatrix} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: board = [ 
	[f, f, f, f],
	[t, t, f, t],
	[f, f, f, f],
	[f, f, f, f] 
], start = board[3][0], end = board[0][0]
Output: 7
Explanation: We have to go from start = bottom left and end = top left. Since we would need to go through `(1, 2)` because there is a wall everywhere else on the second row.

In the diagram above, we can go through green cells, and blocked by red cells. Blue color is the path we take, which shows distance as 7.

and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row.

Similar Problem

Shortest Path in Binary Matrix

Solution

Method 1 - Shortest Path BFS

  1. shortest_path function takes the maze, start coordinates, and end coordinates as input.
  2. It defines directions for movement (up, right, down, left) and initializes a visited matrix to track explored cells.
  3. A queue using deque is used for BFS. It stores tuples of (current coordinate, steps taken).
  4. The algorithm starts at the start coordinate and marks it as visited.
  5. It iterates through the queue, exploring neighbors (up, right, down, left) of the current cell.
  6. For each neighbor, it checks if it’s within bounds, not visited, and not a wall.
  7. If these conditions are met, the neighbor is added to the queue with the updated step count (steps + 1).
  8. The process repeats until the queue is empty or the end coordinate is found.
  9. If the end coordinate is found, the function returns the number of steps taken (shortest path).
  10. If the queue becomes empty without finding the end, it means there’s no path, and the function returns None.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

import java.util.LinkedList;
import java.util.Queue;

class MazeSolver {

	public static Integer findShortestPath(boolean[][] maze, int[] start, int[] end) {
		int rows = maze.length;
		int cols = maze[0].length;

		int[][] distances = new int[rows][cols]; // Stores distance from start for each cell
		for (int[] row: distances) {
			Arrays.fill(row, Integer.MAX_VALUE); // Initialize with infinity
		}

		distances[start[0]][start[1]] = 0; // Mark start distance as 0
		int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Up, right, down, left
		Queue < int[] > queue = new LinkedList<>();
		queue.offer(start);

		while (!queue.isEmpty()) {
			int[] current = queue.poll();
			int row = current[0];
			int col = current[1];

			if (row == end[0] && col == end[1]) {
				return distances[row][col]; // Found the end, return distance
			}

			for (int[] dir: directions) {
				int newRow = row + dir[0];
				int newCol = col + dir[1];

				if (isValid(newRow, newCol, rows, cols) && !maze[newRow][newCol] && distances[newRow][newCol] > distances[row][col] + 1) {
					distances[newRow][newCol] = distances[row][col] + 1; // Update distance
					queue.offer(new int[] {
						newRow, newCol
					});
				}
			}
		}

		return null; // No path found
	}

	private static boolean isValid(int row, int col, int rows, int cols) {
		return 0 <= row && row < rows && 0 <= col && col  <  cols;
	}

	public static void main(String[] args) {
		boolean[][] maze = {
	      {false, false, false, false},
	      {true, true, false, true},
	      {false, false, false, false},
	      {false, false, false, false}
	    };

		int[] start = { 3, 0 };
		int[] end = { 0, 0 };

		Integer shortestPath = findShortestPath(maze, start, end);

		if (shortestPath == null) {
			System.out.println("No path exists");
		} else {
			System.out.println("Shortest path: " + shortestPath + " steps");
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from collections import deque

def shortest_path(maze, start, end):
  rows, cols = len(maze), len(maze[0])
  directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Up, right, down, left
  visited = [[False] * cols for _ in range(rows)]  # Track visited cells

  queue = deque([(start, 0)])  # Queue for BFS (coordinate, steps)
  visited[start[0]][start[1]] = True

  while queue:
    current, steps = queue.popleft()
    if current == end:
      return steps

    for dr, dc in directions:
      new_row, new_col = current[0] + dr, current[1] + dc
      if 0 <= new_row < rows and 0 <= new_col < cols and not visited[new_row][new_col] and not maze[new_row][new_col]:
        # Check if within bounds, not visited, and not a wall
        visited[new_row][new_col] = True
        queue.append(((new_row, new_col), steps + 1))

  return None  # No path found

# Example usage
maze = [
    [False, False, False, False],
    [True, True, False, True],
    [False, False, False, False],
    [False, False, False, False]
]

start = (3, 0)
end = (0, 0)

shortest_distance = shortest_path(maze, start, end)

if shortest_distance is None:
  print("No path exists")
else:
  print(f"Shortest path: {shortest_distance} steps")

Complexity

  • ⏰ Time complexity: O(m*n) where m is number of rows and n is number of columns
  • 🧺 Space complexity: O(m*n) for using visited matrix