The Maze

Medium

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

Given the ball'sstart position, thedestinationand themaze, determine whether the ball could stop at the destination.

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: true

Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2:

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) = (3, 2)

Output: false

Explanation: There is no way for the ball to stop at the destination.

Note:

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

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

3. 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.

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

Analysis

DFS 深度优先搜索

Source: https://leetcode.com/problems/the-maze/solution/

In order to do this traversal, one of the simplest schemes is to undergo depth first search. In this case, we choose one path at a time and try to go as deep as possible into the levels of the tree before going for the next path.

In order to implement this, we make use of a recursive function dfs(maze, start, desination, visited).

注意终止条件：因为记忆化的visited[][]存入的是访问过的位置，而每次进入循环的（除了start）都是停止状态的position；所以如果visited[row][col] == true，就要返回false，说明之前来过，但是还没有找到终点；或者是当前访问位置就是终点位置。

球在不碰到边界和墙之前一直沿着固定方向滚动，因此需要while函数，通过判定是否碰到边界来判断是否继续前进（position + diff）。

BFS 广度优先搜索

we try to explore the search space on a level by level basis. We try to move in all the directions at every step. When all the directions have been explored and we still don't reach the destination, then only we proceed to the new set of traversals from the new positions obtained.

Use queue to implement BFS.

visited[][] for visited positions.

initialize:

queue.offer(start);
visited[start[0]][start[1]] = true;

To get the next "Stopped Position"

 int nrow = pos[0];
 int ncol = pos[1];
 while (canRoll(maze, nrow + dir[0], ncol + dir[1])) {
      nrow += dir[0];  
      ncol += dir[1];  
 }

Trick:

如何得到下一个停止位置（即，可以重新遍历四个方向的位置），在于while循环中，检查的是新的坐标，但是还未更新原有坐标，这样跳出while循环时，得到的就是我们需要的静止坐标 (nrow, ncol)，而不用再减去方向矢量(nrow - dir[0], ncol - dir[1]).

Solution

DFS - ( modularized) - (6ms, 93.42%)

class Solution {

    // UP: {-1, 0}, RIGHT: {0, 1}, DOWN: {1, 0}, LEFT: {0, -1}
    private static int DIR[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];

        return traverse(maze, start, destination, visited);
    }

    private boolean traverse(int[][] maze, int[] position, int[] destination, boolean[][] visited) {
        if (visited[position[0]][position[1]]) {
            return false;
        }
        if (Arrays.equals(position, destination)) {
            return true;
        }

        visited[position[0]][position[1]] = true;

        // Roll the ball for `UP, RIGHT, DOWN, LEFT` four directions
        for (int i = 0; i < DIR.length; i++) {
            int[] newPosition = roll(maze, position, DIR[i]);

            if (traverse(maze, newPosition, destination, visited)) {
                return true;
            }
        }

        return false;
    }


    // Roll the ball based on current position and direction, return new stopped postion
    private int[] roll(int[][] maze, int[] position, int[] direction) {
        int row = position[0];
        int col = position[1];

        while (canRoll(maze, row + direction[0], col + direction[1])) {
            row += direction[0];
            col += direction[1];
        }
        return new int[] {row, col};
    }

    // Using next row, col position to check if a ball can roll
    private boolean canRoll(int[][] maze, int nrow, int ncol) {
        int m = maze.length;
        int n = maze[0].length;

        if (nrow < 0 || nrow >= m || ncol < 0 || ncol >= n) {
            return false;
        }
        if (maze[nrow][ncol] == 1) {
            return false;
        }
        return true;
    }
}

• Time complexity :O(mn). Complete traversal of maze will be done in the worst case. Here, m and n refers to the number of rows and coloumns of the maze.

• Space complexity :O(mn). visited array of size m*n is used.

BFS - (6ms, 84.21%)

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

        queue.offer(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            if (pos[0] == destination[0] && pos[1] == destination[1]) {
                return true;
            }

            for (int[] dir: dirs) {
                int nrow = pos[0];
                int ncol = pos[1];
                while (canRoll(maze, nrow + dir[0], ncol + dir[1])) {
                     nrow += dir[0];  
                     ncol += dir[1];  
                }

                if (!visited[nrow][ncol]) {
                    queue.offer(new int[] {nrow, ncol});
                    visited[nrow][ncol] = true;
                }
            }
        }
        return false;
    }

    private boolean canRoll(int[][] maze, int nrow, int ncol) {
        int m = maze.length;
        int n = maze[0].length;
        return nrow < m && nrow >= 0 && ncol < n && ncol >= 0 && maze[nrow][ncol] == 0;
    }
}

Reference

https://leetcode.com/problems/the-maze/solution/