Problem

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.

思路一（dfs）

写法一

• 四个方向， 每次都碰到壁再继续下去， 没有结束条件， 所以需要用一个visited数组记录碰到的点

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][][] visited = new boolean[maze.length][maze[0].length][4];
        return dfs(maze, start[0], start[1], destination, visited, 0)
            || dfs(maze, start[0], start[1], destination, visited, 1)
            || dfs(maze, start[0], start[1], destination, visited, 2)
            || dfs(maze, start[0], start[1], destination, visited, 3);
    }

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    private boolean dfs(int[][] maze, int x, int y, int[] destination, boolean[][][] visited, int dir) {
        if (x == destination[0] && y == destination[1]) return true;
        if (visited[x][y][dir]) return false;

        visited[x][y][dir] = true;
        while (x >=0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
            x += dx[dir];
            y += dy[dir];
        }
        x -= dx[dir];
        y -= dy[dir];

        return dfs(maze, x, y, destination, visited, 0)
            || dfs(maze, x, y, destination, visited, 1)
            || dfs(maze, x, y, destination, visited, 2)
            || dfs(maze, x, y, destination, visited, 3);
    }

写法二

• visited记录的是每段的起点

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        return dfs(maze, start, destination, new boolean[maze.length][maze[0].length]);
    }

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

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

        for (int i = 0; i < 4; i++) {
            int x = start[0];
            int y = start[1];

            while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
                x += dx[i];
                y += dy[i];

            }

            x -= dx[i];
            y -= dy[i];

            if (dfs(maze, new int[]{x, y}, destination, visited)) return true;
        }
        return false;
    }

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

思路二（bfs）

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

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];    
        queue.offer(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curt = queue.poll();
            if (curt[0] == destination[0] && curt[1] == destination[1]) return true;
            for (int i = 0; i < 4; i++) {
                int x = curt[0];
                int y = curt[1];
                while (canRoll(maze, x + dx[i], y + dy[i])) {
                    x += dx[i];
                    y += dy[i];
                }
                if (visited[x][y]) continue;
                visited[x][y] = true;
                queue.offer(new int[]{x, y});
            }
        }
        return false;
    }

    private boolean canRoll(int[][] maze, int x, int y) {
        if (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0) return true;
        return false;
    }