Medium
题目描述
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个连通分量，且不与任何其它 1 相连。grid 中 恰好 有两座岛。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
示例 1：
输入：grid = [[0,1],[1,0]]
输出：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].length2 <= n <= 100grid[i][j]不是0就是1grid中恰好有两座岛
解题思路
这道题的核心思路是 DFS + BFS 的组合策略。
首先，我们需要找到第一个岛屿，并将其所有格子标记出来。这可以通过 DFS 来实现：遍历矩阵找到第一个为 1 的位置，然后用 DFS 找出整个岛屿的所有位置。
接下来，从第一个岛屿的所有边界位置开始，使用 BFS 向外扩展，寻找最短路径到达第二个岛屿。这里的关键是将第一个岛屿的所有位置都作为 BFS 的起点，这样可以确保找到的是两个岛屿之间的最短距离。
具体步骤：
- 遍历矩阵，找到第一个岛屿的任意一个位置
- 使用 DFS 找出第一个岛屿的所有位置，并将这些位置加入队列作为 BFS 的起点
- 使用 BFS 从第一个岛屿向外扩展，每扩展一步，距离加 1
- 当 BFS 遇到值为 1 的格子时（即第二个岛屿），返回当前距离
这种方法的时间复杂度是 O(n²)，空间复杂度也是 O(n²)，是解决此类"最短路径连接两个区域"问题的经典方法。
代码实现
class Solution {
public:
int shortestBridge(vector<vector<int>>& grid) {
int n = grid.size();
queue<pair<int, int>> q;
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 找到第一个岛屿并用DFS标记
bool 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, q);
found = true;
}
}
}
// BFS找最短路径
int steps = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
auto [x, y] = q.front();
q.pop();
for (auto& dir : dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
return steps;
} else if (grid[nx][ny] == 0) {
grid[nx][ny] = 2;
q.push({nx, ny});
}
}
}
}
steps++;
}
return -1;
}
private:
void dfs(vector<vector<int>>& grid, int x, int y, queue<pair<int, int>>& q) {
int n = grid.size();
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) return;
grid[x][y] = 2;
q.push({x, y});
dfs(grid, x + 1, y, q);
dfs(grid, x - 1, y, q);
dfs(grid, x, y + 1, q);
dfs(grid, x, y - 1, q);
}
};
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
n = len(grid)
q = deque()
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(x, y):
if x < 0 or x >= n or y < 0 or y >= n or grid[x][y] != 1:
return
grid[x][y] = 2
q.append((x, y))
for dx, dy in dirs:
dfs(x + dx, y + dy)
# 找到第一个岛屿并标记
found = False
for i in range(n):
if found:
break
for j in range(n):
if grid[i][j] == 1:
dfs(i, j)
found = True
break
# BFS找最短路径
steps = 0
while q:
size = len(q)
for _ in range(size):
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n:
if grid[nx][ny] == 1:
return steps
elif grid[nx][ny] == 0:
grid[nx][ny] = 2
q.append((nx, ny))
steps += 1
return -1
public class Solution {
public int ShortestBridge(int[][] grid) {
int n = grid.Length;
Queue<(int, int)> q = new Queue<(int, int)>();
int[,] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 找到第一个岛屿并用DFS标记
bool 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, q);
found = true;
}
}
}
// BFS找最短路径
int steps = 0;
while (q.Count > 0) {
int size = q.Count;
for (int i = 0; i < size; i++) {
var (x, y) = q.Dequeue();
for (int d = 0; d < 4; d++) {
int nx = x + dirs[d, 0];
int ny = y + dirs[d, 1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
return steps;
} else if (grid[nx][ny] == 0) {
grid[nx][ny] = 2;
q.Enqueue((nx, ny));
}
}
}
}
steps++;
}
return -1;
}
private void DFS(int[][] grid, int x, int y, Queue<(int, int)> q) {
int n = grid.Length;
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) return;
grid[x][y] = 2;
q.Enqueue((x, y));
DFS(grid, x + 1, y, q);
DFS(grid, x - 1, y, q);
DFS(grid, x, y + 1, q);
DFS(grid, x, y - 1, q);
}
}
var shortestBridge = function(grid) {
const n = grid.length;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
// Find and mark first island
const queue = [];
let found = false;
for (let i = 0; i < n && !found; i++) {
for (let j = 0; j < n && !found; j++) {
if (grid[i][j] === 1) {
dfs(i, j);
found = true;
}
}
}
function dfs(i, j) {
if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] !== 1) return;
grid[i][j] = 2;
queue.push([i, j]);
for (const [di, dj] of directions) {
dfs(i + di, j + dj);
}
}
// BFS to find shortest path to second island
let steps = 0;
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 2) continue;
if (grid[nx][ny] === 1) return steps;
grid[nx][ny] = 2;
queue.push([nx, ny]);
}
}
steps++;
}
return steps;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n²)，需要遍历整个矩阵进行DFS和BFS |
| 空间复杂度 | O(n²)，队列最多存储O(n²)个位置，DFS递归栈深度最多为O(n²) |