934. Shortest Bridge
题目文本会按所选界面语言从俄语翻译；代码保持不变。
Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. return наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.
示例:
Input: grid = [[0,1],[1,0]]
Output: 1
C# 解法
匹配/原始using System;
using System.Collections.Generic;
public class Solution {
public int ShortestBridge(int[][] grid) {
int n = grid.Length;
var directions = new int[][] {
new int[] {-1, 0},
new int[] {1, 0},
new int[] {0, -1},
new int[] {0, 1}
};
var queue = new Queue<int[]>();
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, queue);
found = true;
}
}
}
int steps = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; ++i) {
var point = queue.Dequeue();
int x = point[0], y = point[1];
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
return steps;
}
if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
queue.Enqueue(new int[] {nx, ny});
}
}
}
}
steps++;
}
return -1;
}
private void Dfs(int[][] grid, int x, int y, Queue<int[]> queue) {
int n = grid.Length;
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) {
return;
}
grid[x][y] = -1;
queue.Enqueue(new int[] {x, y});
Dfs(grid, x - 1, y, queue);
Dfs(grid, x + 1, y, queue);
Dfs(grid, x, y - 1, queue);
Dfs(grid, x, y + 1, queue);
}
}C++ 解法
自动草稿，提交前请检查#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int ShortestBridge(int[][] grid) {
int n = grid.size();
var directions = new int[][] {
new int[] {-1, 0},
new int[] {1, 0},
new int[] {0, -1},
new int[] {0, 1}
};
var queue = new queue<int[]>();
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, queue);
found = true;
}
}
}
int steps = 0;
while (queue.size() > 0) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
var point = queue.Dequeue();
int x = point[0], y = point[1];
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
return steps;
}
if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
queue.Enqueue(new int[] {nx, ny});
}
}
}
}
steps++;
}
return -1;
}
private void Dfs(int[][] grid, int x, int y, queue<int[]> queue) {
int n = grid.size();
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) {
return;
}
grid[x][y] = -1;
queue.Enqueue(new int[] {x, y});
Dfs(grid, x - 1, y, queue);
Dfs(grid, x + 1, y, queue);
Dfs(grid, x, y - 1, queue);
Dfs(grid, x, y + 1, queue);
}
}Java 解法
自动草稿，提交前请检查import java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
public int ShortestBridge(int[][] grid) {
int n = grid.length;
var directions = new int[][] {
new int[] {-1, 0},
new int[] {1, 0},
new int[] {0, -1},
new int[] {0, 1}
};
var queue = new LinkedList<int[]>();
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 steps = 0;
while (queue.size() > 0) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
var point = queue.poll();
int x = point[0], y = point[1];
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
return steps;
}
if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
queue.Enqueue(new int[] {nx, ny});
}
}
}
}
steps++;
}
return -1;
}
private void Dfs(int[][] grid, int x, int y, Queue<int[]> queue) {
int n = grid.length;
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) {
return;
}
grid[x][y] = -1;
queue.Enqueue(new int[] {x, y});
Dfs(grid, x - 1, y, queue);
Dfs(grid, x + 1, y, queue);
Dfs(grid, x, y - 1, queue);
Dfs(grid, x, y + 1, queue);
}
}JavaScript 解法
匹配/原始var shortestBridge = function(grid) {
const n = grid.length;
const neighbors = (x, y) => {
return [[-1, 0], [1, 0], [0, -1], [0, 1]].map(([dx, dy]) => [x + dx, y + dy]).filter(([nx, ny]) => 0 <= nx && nx < n && 0 <= ny && ny < n);
};
const bfs = (queue) => {
let visited = new Set(queue.map(([x, y]) => `${x},${y}`));
let steps = 0;
while (queue.length > 0) {
const newQueue = [];
for (const [x, y] of queue) {
for (const [nx, ny] of neighbors(x, y)) {
if (!visited.has(`${nx},${ny}`)) {
if (grid[nx][ny] === 1) {
return steps;
}
visited.add(`${nx},${ny}`);
newQueue.push([nx, ny]);
}
}
}
queue = newQueue;
steps++;
}
return -1;
};
const findFirstIsland = () => {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
const queue = [[i, j]];
grid[i][j] = -1;
const island = [[i, j]];
while (queue.length > 0) {
const [x, y] = queue.shift();
for (const [nx, ny] of neighbors(x, y)) {
if (grid[nx][ny] === 1) {
grid[nx][ny] = -1;
queue.push([nx, ny]);
island.push([nx, ny]);
}
}
}
return island;
}
}
}
return [];
};
const island = findFirstIsland();
return bfs(island);
};Go 解法
匹配/原始package main
type Pair struct {
x, y int
}
func shortestBridge(grid [][]int) int {
n := len(grid)
directions := [][]int{
{-1, 0},
{1, 0},
{0, -1},
{0, 1},
}
queue := []Pair{}
found := false
var dfs func(x, y int)
dfs = func(x, y int) {
if x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1 {
return
}
grid[x][y] = -1
queue = append(queue, Pair{x, y})
for _, dir := range directions {
nx, ny := x+dir[0], y+dir[1]
dfs(nx, ny)
}
}
for i := 0; i < n && !found; i++ {
for j := 0; j < n && !found; j++ {
if grid[i][j] == 1 {
dfs(i, j)
found = true
}
}
}
steps := 0
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
p := queue[0]
queue = queue[1:]
for _, dir := range directions {
nx, ny := p.x+dir[0], p.y+dir[1]
if nx >= 0 && nx < n && ny >= 0 && ny < n {
if grid[nx][ny] == 1 {
return steps
}
if grid[nx][ny] == 0 {
grid[nx][ny] = -1
queue = append(queue, Pair{nx, ny})
}
}
}
}
steps++
}
return -1
}Algorithm
1⃣find все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.
2⃣Использовать BFS для расширения из каждой клетки первого острова, чтобы find 最短路径 к клетке второго острова.
3⃣Вернуть длину кратчайшего пути.
😎
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.
目前还没有活跃职位。