DevExCode

LeetCode 490: The Maze

ArrayDepth-First SearchBreadth-First SearchMatrix

Problem Description

Explanation:

The problem "The Maze" can be solved using a breadth-first search (BFS) algorithm. The idea is to start from the starting position and explore all possible directions until we reach the destination. We will keep track of the visited positions to avoid revisiting them.

Here are the steps to solve the problem:

  1. Initialize a queue to store the positions to be explored.
  2. Add the starting position to the queue.
  3. While the queue is not empty:
    • Remove the position from the front of the queue.
    • Check if this position is the destination. If it is, return true.
    • Explore all possible directions (up, down, left, right) from the current position.
    • Move in each direction until hitting a wall or the edge of the maze.
    • If the destination is reached in any direction, add the new position to the queue.
  4. If the queue becomes empty and the destination is not reached, return false.

The time complexity of this algorithm is O(mn) where m is the number of rows and n is the number of columns in the maze. The space complexity is also O(mn) due to the queue used for BFS.

: :

View on LeetCode

Solutions

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length, n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            
            if (curr[0] == destination[0] && curr[1] == destination[1]) {
                return true;
            }
            
            for (int[] dir : dirs) {
                int x = curr[0] + dir[0];
                int y = curr[1] + dir[1];
                
                while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                }
                
                if (!visited[x - dir[0]][y - dir[1]]) {
                    queue.offer(new int[]{x - dir[0], y - dir[1]});
                    visited[x - dir[0]][y - dir[1]] = true;
                }
            }
        }
        
        return false;
    }
}

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...