ORID 56 DFS the maze

490 the maze 解题报告
这道题我做的时候没看清楚题意，所以导致了一开始的思路有问题。我以为像backtrack那样，因为之前做过robot room cleaner这种题，以为每次可以上下左右四个方向选择走一个，走过去之后还可以退回来。
但这道题是这个球它往一个方向走之后不能停下来。所以你用backtrack的思路去做的话是不对的。所以有时候看清题目是挺重要的，因为之前好几次OA的时候我也是因为题目没注意，导致了自己代码里有个小错误，debug了半天。这样实际上浪费很多时间，所以amazon之前那个人展示的时候是非常对的，你写完一部分之后先跑一下看看，没有问题之后在继续，这样保证你之前的代码不会影响到之后的，节省了debug的时间。说跑题了。
这道题DFS或者BFS都可以做，我觉得DFS更加好理解一点，所以先用DFS做一遍
这题主要的思路就是先用while loop把一条路“打通”，然后在用DFS检查这条路上有没有你目的地的坐标。

while (r < maze.length && maze[start[0]][r] == 0) {
  r++;
}

这一段代码实际上就是在说，如果往右走还没遇到墙（当前这个数值==0 就代表可以走，maze[x][y]==1代表墙），那就一直把r这个坐标往右推。然后再通过DFS来往回查找（不知道这算不算回溯……）

if (dfs(maze, new int[] {start[0], r - 1}, destination, visited) {
  return true;
}

这里就是把start[][] 这个起点位置往回走一个，然后检查当前坐标是否是我们想要的终点。（dfs本身出口就是检查是否为终点）不是的话什么都不做。
理解了一个方向，那么剩下的四个方向思路是一样的。下面是代码

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {        
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return dfs(maze, start, destination, visited);
    }
    private boolean dfs(int[][] maze, int[] start, int[] destination, boolean[][] visited) {
        if (visited[start[0]][start[1]]) {
            return false;
        }
        if (start[0] == destination[0] && start[1] == destination[1]) {
            return true;
        }
        visited[start[0]][start[1]] = true;
        int r = start[1] + 1, l = start[1] - 1, u = start[0] - 1, d = start[0] + 1;
        while (r < maze[0].length && maze[start[0]][r] == 0) {
            r++;
        }
        if (dfs(maze, new int[] {start[0], r - 1}, destination, visited)) {
            return true;
        }
        while (l >= 0 && maze[start[0]][l] == 0) {
            l--;
        }
        if (dfs(maze, new int[] {start[0], l + 1}, destination, visited)) {
            return true;
        }
        while (u >= 0 && maze[u][start[1]] == 0) {
            u--;
        }
        if (dfs(maze, new int[] {u + 1, start[1]}, destination, visited)) {
            return true;
        }
        while (d < maze.length && maze[d][start[1]] == 0) {
            d++;
        }
        if (dfs(maze, new int[] {d - 1, start[1]}, destination, visited)) {
            return true;
        }
        return false;
    }

时空复杂度

这题答案写的时空复杂度是O(mn) m是行数，n列数。