934. 最短的桥

题目描述

输入一个 n x n 的矩阵 grid，1 代表陆地，0 代表水。

上下左右相邻的陆地连成一块，一块极大的连通陆地称为一座岛。grid 中正好有两座岛。

你可以把任意多个 0 改成 1。返回让两座岛连成一座岛最少需要改动多少个 0。

示例 1

输入：grid = [[0,1],[1,0]]
输出：1

解释：改动 (0,0) 或 (1,1) 中的一个即可相连。

示例 2

输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

解释：两座岛在对角，至少要填两格水才能连通。

示例 3

输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

解释：中间的小岛与外圈只隔一格水，填一格即可。

数据范围

n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j] 只会是 0 或 1。
grid 中恰好有两座岛。

解题思路

先用 DFS 找出第一座岛，把它的格子全部标成 2，并全部放进 frontier 作为 BFS 的起点。然后做多源 BFS，一层一层向海里扩展：每扩展一层 steps 加 1，新到达的海洋格也标成 2。一旦扩展时碰到值为 1 的格子，就说明到达了第二座岛，当前的 steps 就是需要翻转的 0 的数目。

为什么正确

第 steps 轮开始时，frontier 中的格子与第一座岛的距离都是 steps（第一座岛自身的距离为 0），且它们都已标成 2。

复杂度分析

时间 O(n²)：DFS 和 BFS 都只访问每个格子常数次。空间 O(n²)。

易错点

必须把第一座岛的所有格子同时作为起点（多源 BFS），而不是只从一个格子出发；并且碰到 1 时返回的是当前层数 steps，而不是 steps+1，因为第一座岛周围的第 0 层邻居还没被翻转。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        start = next((r, c) for r in range(n) for c in range(n) if grid[r][c] == 1)
        grid[start[0]][start[1]] = 2
        stack = [start]
        frontier = [start]
        while stack:
            x, y = stack.pop()
            for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    stack.append((nx, ny))
                    frontier.append((nx, ny))
        steps = 0
        while frontier:
            nxt = []
            for x, y in frontier:
                for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= nx < n and 0 <= ny < n:
                        if grid[nx][ny] == 1:
                            return steps
                        if grid[nx][ny] == 0:
                            grid[nx][ny] = 2
                            nxt.append((nx, ny))
            frontier = nxt
            steps += 1
        return -1

class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        int[] start = null;
        for (int r = 0; r < n && start == null; r++) for (int c = 0; c < n; c++) if (grid[r][c] == 1) { start = new int[]{r, c}; break; }
        grid[start[0]][start[1]] = 2;
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(start);
        List<int[]> frontier = new ArrayList<>();
        frontier.add(start);
        int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
        while (!stack.isEmpty()) {
            int[] p = stack.pop();
            for (int d = 0; d < 4; d++) {
                int nx = p[0] + dx[d], ny = p[1] + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    stack.push(new int[]{nx, ny});
                    frontier.add(new int[]{nx, ny});
                }
            }
        }
        int steps = 0;
        while (!frontier.isEmpty()) {
            List<int[]> nxt = new ArrayList<>();
            for (int[] p : frontier) {
                for (int d = 0; d < 4; d++) {
                    int nx = p[0] + dx[d], ny = p[1] + dy[d];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                        if (grid[nx][ny] == 1) {
                            return steps;
                        }
                        if (grid[nx][ny] == 0) {
                            grid[nx][ny] = 2;
                            nxt.add(new int[]{nx, ny});
                        }
                    }
                }
            }
            frontier = nxt;
            steps++;
        }
        return -1;
    }
}

class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        pair<int,int> start;
        for (int r = 0, f = 0; r < n && !f; r++) for (int c = 0; c < n; c++) if (grid[r][c] == 1) { start = {r, c}; f = 1; break; }
        grid[start.first][start.second] = 2;
        vector<pair<int,int>> stk = {start};
        vector<pair<int,int>> frontier = {start};
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        while (!stk.empty()) {
            auto [x, y] = stk.back(); stk.pop_back();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    stk.push_back({nx, ny});
                    frontier.push_back({nx, ny});
                }
            }
        }
        int steps = 0;
        while (!frontier.empty()) {
            vector<pair<int,int>> nxt;
            for (auto [x, y] : frontier) {
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                        if (grid[nx][ny] == 1) {
                            return steps;
                        }
                        if (grid[nx][ny] == 0) {
                            grid[nx][ny] = 2;
                            nxt.push_back({nx, ny});
                        }
                    }
                }
            }
            frontier = nxt;
            steps++;
        }
        return -1;
    }
};

func shortestBridge(grid [][]int) int {
	n := len(grid)
	var start [2]int
	found := false
	for r := 0; r < n && !found; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 1 {
				start = [2]int{r, c}
				found = true
				break
			}
		}
	}
	grid[start[0]][start[1]] = 2
	stack := [][2]int{start}
	frontier := [][2]int{start}
	dx := []int{1, -1, 0, 0}
	dy := []int{0, 0, 1, -1}
	for len(stack) > 0 {
		p := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		for d := 0; d < 4; d++ {
			nx, ny := p[0]+dx[d], p[1]+dy[d]
			if nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1 {
				grid[nx][ny] = 2
				stack = append(stack, [2]int{nx, ny})
				frontier = append(frontier, [2]int{nx, ny})
			}
		}
	}
	steps := 0
	for len(frontier) > 0 {
		nxt := [][2]int{}
		for _, p := range frontier {
			for d := 0; d < 4; d++ {
				nx, ny := p[0]+dx[d], p[1]+dy[d]
				if nx >= 0 && nx < n && ny >= 0 && ny < n {
					if grid[nx][ny] == 1 {
						return steps
					}
					if grid[nx][ny] == 0 {
						grid[nx][ny] = 2
						nxt = append(nxt, [2]int{nx, ny})
					}
				}
			}
		}
		frontier = nxt
		steps++
	}
	return -1
}

var shortestBridge = function(grid) {
    const n = grid.length;
    let start = [];
    outer: for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) if (grid[r][c] === 1) { start = [[r, c]]; break outer; }
    const [sr, sc] = start[0];
    grid[sr][sc] = 2;
    const stack = [[sr, sc]];
    let frontier = [[sr, sc]];
    const D = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    while (stack.length > 0) {
        const [x, y] = stack.pop();
        for (const [a, b] of D) {
            const nx = x + a, ny = y + b;
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] === 1) {
                grid[nx][ny] = 2;
                stack.push([nx, ny]);
                frontier.push([nx, ny]);
            }
        }
    }
    let steps = 0;
    while (frontier.length > 0) {
        const nxt = [];
        for (const [x, y] of frontier) {
            for (const [a, b] of D) {
                const nx = x + a, ny = y + b;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (grid[nx][ny] === 1) {
                        return steps;
                    }
                    if (grid[nx][ny] === 0) {
                        grid[nx][ny] = 2;
                        nxt.push([nx, ny]);
                    }
                }
            }
        }
        frontier = nxt;
        steps++;
    }
    return -1;
};

function shortestBridge(grid: number[][]): number {
    const n = grid.length;
    let start: number[][] = [];
    outer: for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) if (grid[r][c] === 1) { start = [[r, c]]; break outer; }
    const [sr, sc] = start[0];
    grid[sr][sc] = 2;
    const stack = [[sr, sc]];
    let frontier = [[sr, sc]];
    const D = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    while (stack.length > 0) {
        const [x, y] = stack.pop()!;
        for (const [a, b] of D) {
            const nx = x + a, ny = y + b;
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] === 1) {
                grid[nx][ny] = 2;
                stack.push([nx, ny]);
                frontier.push([nx, ny]);
            }
        }
    }
    let steps = 0;
    while (frontier.length > 0) {
        const nxt: number[][] = [];
        for (const [x, y] of frontier) {
            for (const [a, b] of D) {
                const nx = x + a, ny = y + b;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (grid[nx][ny] === 1) {
                        return steps;
                    }
                    if (grid[nx][ny] === 0) {
                        grid[nx][ny] = 2;
                        nxt.push([nx, ny]);
                    }
                }
            }
        }
        frontier = nxt;
        steps++;
    }
    return -1;
}

载入编辑器，自己跑一遍 →

图论专题的其他题目

查看图论全部题目 →