490. The Maze 的BFS和DFS的两种做法

这题是问能不能到目标点，最优解应该是BFS。
当然DFS+ early return也能做， 但是DFS可能运气很差，瞎找了很久才找到你要的端点。
先帖一个DFS + memo + early return的代码，效果也不是那么差。
这段代码是我考试时写的，当时函数头和leetcode上不一样，所以这里我又包了一下，所以看起来有点奇怪。

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int N = maze.length, M = maze[0].length;
        char[][] mazec = new char[N][M];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                mazec[r][c] = (char) (maze[r][c] + '0');
            }
        }
        return canReach(mazec, start[0], start[1], destination[0], destination[1]);
    }
    int[][] OFFSETS;
    public boolean canReach(char[][] maze, int sr, int sc, int dr, int dc) {
        Map<Integer, Integer> states = new HashMap<>(); 
        // null not visited, 1, visiting, 2, visited can't find, 3 visited can find;
        OFFSETS = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        return dfs(maze, sr, sc, dr, dc, states);
    }
    private boolean dfs(char[][] maze, int sr,int sc, int dr, int dc,  Map<Integer, Integer> states ) {
        int code = sr * 100 + sc;
        if (states.getOrDefault(code, 0) == 1) return false;
        if (states.getOrDefault(code, 0) >= 2) return states.get(code) == 3; // can find 
        states.put(code, 1); // set it to visiting
        if (sr == dr && sc == dc) {
            states.put(code, 3);
            return true;
    }
        List<int[]> reachableLocations = getReachableLocations(maze, sr, sc);
        for (int[] reachableLocation : reachableLocations) {
            int nextR = reachableLocation[0], nextC = reachableLocation[1];

            if ( dfs(maze, nextR, nextC, dr, dc, states)) {
                states.put(code, 3); // visited can find;
                return true;
            }
        }
        states.put(code, 2); // visited, can't find
        return false;
    }
    private List<int[]> getReachableLocations(char[][] grid, int sr, int sc) {
        List<int[]> ans = new ArrayList<>();

        for (int[] os : OFFSETS) {
            int r = sr, c = sc;
            while (r + os[0] >= 0 && r + os[0] < grid.length && 
                c + os[1] >= 0 && c + os[1] < grid[0].length &&
                grid[r + os[0]][c + os[1]] != '1') {
            r += os[0];
            c += os[1];
            }
            if (r != sr || c != sc) {
                ans.add(new int[]{r, c});
            }
        }
    return ans;
    }

}

但是这题用DFS就有点没必要了，用最基本的BFS就可以了。
不要太简单

class Solution {
    int[][] OFFSETS;
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int N = maze.length, M = maze[0].length;
        OFFSETS = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            for (int[] nextPos : getNext(pos, maze, N, M)) {
                int nr = nextPos[0], nc = nextPos[1];
                if (visited[nr][nc]) continue;
                visited[nr][nc] = true;
                queue.offer(nextPos);
                if (Arrays.equals(nextPos, destination)) return true;
            }
        }
        return false;
    }
    private List<int[]> getNext(int[] pos, int[][] maze, int N, int M) {
        int r = pos[0], c = pos[1];
        List<int[]> ans = new ArrayList<>();
        for (int[] os : OFFSETS) {
            int nr = r, nc = c;
            while (nr + os[0] >= 0 && nc + os[1] >= 0 &&
                  nr + os[0] < N && nc + os[1] < M && 
                  maze[nr + os[0]][nc + os[1]] == 0) {
                nr += os[0];
                nc += os[1];
            }
            if (nr != r || nc != c) ans.add(new int[]{nr, nc});
        }
        return ans;
    }
}