490.The Maze (M)

1.Description(Medium)

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.

2.Code

经典DFS题目

这道题让我们遍历迷宫，但是与以往不同的是，这次迷宫是有一个滚动的小球，这样就不是每次只走一步了，而是朝某一个方向一直滚，直到遇到墙或者边缘才停下来，我记得貌似之前在手机上玩过类似的游戏。那么其实还是要用DFS或者BFS来解，只不过需要做一些修改。先来看DFS的解法，我们用DFS的同时最好能用上优化，即记录中间的结果，这样可以避免重复运算，提高效率。我们用二维数组dp来保存中间结果，然后用maze数组本身通过将0改为-1来记录某个点是否被访问过，这道题的难点是在于处理一直滚的情况，其实也不难，只要我们有了方向，只要一直在那个方向上往前走，每次判读是否越界了或者是否遇到墙了即可，然后对于新位置

public static boolean flag=false;
    int[] dx={0,0,-1,1};
    int[] dy={-1,1,0,0};
    public boolean hasPath(int[][] maze,int[] start,int[] destination){
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        dfs(start[0], start[1], destination, maze, visited);
        return flag;
    }

    public void dfs(int x,int y,int[] destination,int[][] maze,boolean[][] visited){
        if (x == destination[0] && y == destination[1]) {
            flag = true;
            return;
        }
        if(visited[x][y]) return;
        visited[x][y] = true;

        for(int i=0;i<4;i++){
            int currentx=x+dx[i];
            int currenty=y+dy[i];

                while(!border(currentx, currenty, maze) && maze[currentx][currenty] == 0) {
                    currentx = currentx + dx[i];
                    currenty = currenty + dy[i];
                }
                int newx = currentx - dx[i];
                int newy = currenty - dy[i];
                if(!flag) dfs(newx, newy, destination, maze, visited);
        }

    }

    public boolean border(int x,int y,int[][] maze){
        if(x>=maze.length || y>=maze[0].length || x<0 || y<0){
            return true;
        }
        return false;
    }