图 DFS 进阶：全排列与回路检测

被围绕的区域（LeetCode 130）

与边界相连的 'O' 不会被捕获；先从边界 DFS 标记，再替换：

public void solve(char[][] board) {
    int m = board.length, n = board[0].length;
    // 从四条边界出发，将与边界相连的 'O' 标记为 '#'
    for (int i = 0; i < m; i++) { dfs(board, i, 0); dfs(board, i, n-1); }
    for (int j = 0; j < n; j++) { dfs(board, 0, j); dfs(board, m-1, j); }
    // 扫描：未标记的 'O' → 'X'，'#' → 'O' 恢复
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '#') board[i][j] = 'O';
        }
}
private void dfs(char[][] board, int r, int c) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != 'O') return;
    board[r][c] = '#';
    dfs(board, r+1, c); dfs(board, r-1, c); dfs(board, r, c+1); dfs(board, r, c-1);
}

太平洋大西洋水流问题（LeetCode 417）

逆向思考：水从海边向内"上坡"流（只要高度不低于上一个），找两个大洋都能到达的格子：

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pacific = new boolean[m][n];
    boolean[][] atlantic = new boolean[m][n];
    // 从太平洋边界出发 BFS/DFS
    for (int i = 0; i < m; i++) { dfs(heights, pacific, i, 0); dfs(heights, atlantic, i, n-1); }
    for (int j = 0; j < n; j++) { dfs(heights, pacific, 0, j); dfs(heights, atlantic, m-1, j); }
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (pacific[i][j] && atlantic[i][j]) result.add(Arrays.asList(i, j));
    return result;
}
private void dfs(int[][] h, boolean[][] visited, int r, int c) {
    if (visited[r][c]) return;
    visited[r][c] = true;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length
                && !visited[nr][nc] && h[nr][nc] >= h[r][c])
            dfs(h, visited, nr, nc);
    }
}

克隆图（LeetCode 133）

BFS 或 DFS 克隆，用 HashMap 存旧节点到新节点的映射（避免重复克隆）：

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> cloned = new HashMap<>();
    Queue<Node> queue = new ArrayDeque<>();
    queue.offer(node);
    cloned.put(node, new Node(node.val));
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node neighbor : cur.neighbors) {
            if (!cloned.containsKey(neighbor)) {
                cloned.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            cloned.get(cur).neighbors.add(cloned.get(neighbor));
        }
    }
    return cloned.get(node);
}

总结