827. Making A Large Island
leetcode
#array#csharp#graph#hash-table#leetcode#math#matrix
Task
: hard
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
C# solution
matched/originalpublic class Solution {
private static readonly int[] dr = { -1, 0, 1, 0 };
private static readonly int[] dc = { 0, -1, 0, 1 };
private int[][] grid;
private int N;
public int LargestIsland(int[][] grid) {
this.grid = grid;
N = grid.Length;
int index = 2;
int[] area = new int[N * N + 2];
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
if (grid[r][c] == 1) {
area[index] = Dfs(r, c, index++);
}
}
}
int ans = area.Max();
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
if (grid[r][c] == 0) {
HashSet<int> seen = new HashSet<int>();
foreach (var move in Neighbors(r, c)) {
if (grid[move.Item1][move.Item2] > 1) {
seen.Add(grid[move.Item1][move.Item2]);
}
}
int bns = 1;
foreach (int i in seen) bns += area[i];
ans = Math.Max(ans, bns);
}
}
}
return ans;
}
private int Dfs(int r, int c, int index) {
int ans = 1;
grid[r][c] = index;
foreach (var move in Neighbors(r, c)) {
if (grid[move.Item1][move.Item2] == 1) {
grid[move.Item1][move.Item2] = index;
ans += Dfs(move.Item1, move.Item2, index);
}
}
return ans;
}
private IEnumerable<(int, int)> Neighbors(int r, int c) {
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
yield return (nr, nc);
}
}
}
}C++ solution
auto-draft, review before submit#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:
private static readonly vector<int>& dr = { -1, 0, 1, 0 };
private static readonly vector<int>& dc = { 0, -1, 0, 1 };
private int[][] grid;
private int N;
public int LargestIsland(int[][] grid) {
this.grid = grid;
N = grid.size();
int index = 2;
vector<int>& area = new int[N * N + 2];
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
if (grid[r][c] == 1) {
area[index] = Dfs(r, c, index++);
}
}
}
int ans = area.Max();
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
if (grid[r][c] == 0) {
HashSet<int> seen = new HashSet<int>();
foreach (var move in Neighbors(r, c)) {
if (grid[move.Item1][move.Item2] > 1) {
seen.push_back(grid[move.Item1][move.Item2]);
}
}
int bns = 1;
foreach (int i in seen) bns += area[i];
ans = max(ans, bns);
}
}
}
return ans;
}
private int Dfs(int r, int c, int index) {
int ans = 1;
grid[r][c] = index;
foreach (var move in Neighbors(r, c)) {
if (grid[move.Item1][move.Item2] == 1) {
grid[move.Item1][move.Item2] = index;
ans += Dfs(move.Item1, move.Item2, index);
}
}
return ans;
}
private IEnumerable<(int, int)> Neighbors(int r, int c) {
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
yield return (nr, nc);
}
}
}
}Java solution
matched/originalclass Solution {
int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};
int[][] grid;
int N;
public int largestIsland(int[][] grid) {
this.grid = grid;
N = grid.length;
int index = 2;
int[] area = new int[N*N + 2];
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c)
if (grid[r][c] == 1)
area[index] = dfs(r, c, index++);
int ans = 0;
for (int x: area) ans = Math.max(ans, x);
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c)
if (grid[r][c] == 0) {
Set<Integer> seen = new HashSet();
for (Integer move: neighbors(r, c))
if (grid[move / N][move % N] > 1)
seen.add(grid[move / N][move % N]);
int bns = 1;
for (int i: seen) bns += area[i];
ans = Math.max(ans, bns);
}
return ans;
}
public int dfs(int r, int c, int index) {
int ans = 1;
grid[r][c] = index;
for (Integer move: neighbors(r, c)) {
if (grid[move / N][move % N] == 1) {
grid[move / N][move % N] = index;
ans += dfs(move / N, move % N, index);
}
}
return ans;
}
public List<Integer> neighbors(int r, int c) {
List<Integer> ans = new ArrayList();
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0 <= nr && nr < N && 0 <= nc && nc < N)
ans.add(nr * N + nc);
}
return ans;
}Python solution
matched/originalclass Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(r, c, index):
ans = 1
grid[r][c] = index
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = index
ans += dfs(nr, nc, index)
return ans
def neighbors(r, c):
for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
N = len(grid)
index = 2
area = [0] * (N * N + 2)
for r in range(N):
for c in range(N):
if grid[r][c] == 1:
area[index] = dfs(r, c, index)
index += 1
ans = max(area)
for r in range(N):
for c in range(N):
if grid[r][c] == 0:
seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
ans = max(aGo solution
matched/originalfunc largestIsland(grid [][]int) int {
N := len(grid)
directions := [][]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
area := make([]int, N*N+2)
index := 2
var dfs func(r, c, index int) int
dfs = func(r, c, index int) int {
ans := 1
grid[r][c] = index
for _, d := range directions {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] == 1 {
grid[nr][nc] = index
ans += dfs(nr, nc, index)
}
}
return ans
}
for r := 0; r < N; r++ {
for c := 0; c < N; c++ {
if grid[r][c] == 1 {
area[index] = dfs(r, c, index)
index++
}
}
}
ans := 0
for _, a := range area {
if a > ans {
ans = a
}
}
for r := 0; r < N; r++ {
for c := 0; c < N; c++ {
if grid[r][c] == 0 {
seen := make(map[int]struct{})
for _, d := range directions {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] > 1 {
seen[grid[nr][nc]] = struct{}{}
}
}
bns := 1
for i := range seen {
bns += area[i]
}
if bns > ans {
ans = bns
}
}
}
}
return ans
}Explanation
Algorithm
Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.
Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.
Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.
😎