LeetCode 934. 最短的桥

Categories:

题目描述
思路分析
1. 解法一：DFS + BFS（推荐）
相似题目

题目描述

✅ 934. 最短的桥

思路分析

解法一：DFS + BFS（推荐）

核心思路：

先 DFS 标记其中一座岛，并将其所有格子入队。

从该岛边界开始 BFS 向外扩展，遇到另一座岛时返回步数。

BFS 层数即需要翻转的 0 数量。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示网格边长。

空间复杂度：O(n^2)。

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean found = false;

        for (int i = 0; i < n && !found; i++) {
            for (int j = 0; j < n && !found; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, queue);
                    found = true;
                }
            }
        }

        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int k = 0; k < 4; k++) {
                    int nr = cur[0] + dr[k];
                    int nc = cur[1] + dc[k];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                        continue;
                    }
                    if (grid[nr][nc] == 1) {
                        return steps;
                    }
                    if (grid[nr][nc] == 0) {
                        grid[nr][nc] = 2;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            steps++;
        }

        return -1;
    }

    private void dfs(int[][] grid, int r, int c, Queue<int[]> queue) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != 1) {
            return;
        }
        grid[r][c] = 2;
        queue.offer(new int[]{r, c});

        dfs(grid, r + 1, c, queue);
        dfs(grid, r - 1, c, queue);
        dfs(grid, r, c + 1, queue);
        dfs(grid, r, c - 1, queue);
    }
}

func shortestBridge(grid [][]int) int {
	n := len(grid)
	queue := make([][2]int, 0)
	found := false

	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1 {
			return
		}
		grid[r][c] = 2
		queue = append(queue, [2]int{r, c})

		dfs(r+1, c)
		dfs(r-1, c)
		dfs(r, c+1)
		dfs(r, c-1)
	}

	for i := 0; i < n && !found; i++ {
		for j := 0; j < n && !found; j++ {
			if grid[i][j] == 1 {
				dfs(i, j)
				found = true
			}
		}
	}

	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	steps := 0
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]
			for _, d := range dirs {
				nr, nc := cur[0]+d[0], cur[1]+d[1]
				if nr < 0 || nr >= n || nc < 0 || nc >= n {
					continue
				}
				if grid[nr][nc] == 1 {
					return steps
				}
				if grid[nr][nc] == 0 {
					grid[nr][nc] = 2
					queue = append(queue, [2]int{nr, nc})
				}
			}
		}
		steps++
	}

	return -1
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS
1091. 二进制矩阵中的最短路径	中等	BFS
994. 腐烂的橘子	中等	BFS
934. 最短的桥	中等	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/18390339