标记或并查集，深度优先搜索，广度优先搜索遍历，用哈希集合去重，2 解法，求解《827. 最大人工岛》
例题
827. 最大人工岛
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1:
输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:
输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:
输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
提示：
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1
答案
标记 · 深度优先搜索
var largestIsland = function(grid) {
const n = grid.length, dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
const tags = new Uint32Array(n ** 2), areas = new Uint32Array(n ** 2)
let r = 0, tag = 1
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) areas[tag] = dfs(grid, n, i, j, tags, tag++, dr)
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) continue
const s = new Set
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
s.add(tags[nx * n + ny])
}
let area = 1
for (const tag of s) area += areas[tag]
r = Math.max(r, area)
}
}
return r === 0 ? n ** 2 : r
};
const dfs = (grid, n, x, y, tags, tag, dr) => {
const index = x * n + y
if (tags[index] !== 0) return 0
tags[index] = tag
let r = 1
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
r += dfs(grid, n, nx, ny, tags, tag, dr)
}
return r
}function largestIsland(grid: number[][]): number {
const n = grid.length, dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
const tags = new Array(n ** 2).fill(0), areas = new Array(n ** 2).fill(0)
let r = 0, tag = 1
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) areas[tag] = dfs(grid, n, i, j, tags, tag++, dr)
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) continue
const s = new Set<number>();
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
s.add(tags[nx * n + ny])
}
let area = 1
for (const tag of s) area += areas[tag]
r = Math.max(r, area)
}
}
return r === 0 ? n ** 2 : r
};
const dfs = (grid: number[][], n: number, x: number, y: number, tags: number[], tag: number, dr: number[][]) => {
const index = x * n + y
if (tags[index] !== 0) return 0
tags[index] = tag
let r = 1
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
r += dfs(grid, n, nx, ny, tags, tag, dr)
}
return r
}class Solution {
function largestIsland($grid) {
$n = count($grid);
$tags = array_fill(0, $n * $n, 0);
$areas = array_fill(0, $n * $n, 0);
$r = 0;
$tag = 1;
$dr = [[0, 1], [1, 0], [0, -1], [-1, 0]];
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($grid[$i][$j] === 1) {
$areas[$tag] = $this->dfs($grid, $n, $i, $j, $tags, $tag, $dr);
$tag++;
}
}
}
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($grid[$i][$j] === 0) {
$s = array();
foreach ($dr as $d) {
$nx = $i + $d[0];
$ny = $j + $d[1];
if ($nx < 0 || $nx >= $n || $ny < 0 || $ny >= $n || $grid[$nx][$ny] === 0) continue;
if (in_array($tags[$nx * $n + $ny], $s) === false) $s []= $tags[$nx * $n + $ny];
}
$area = 1;
foreach ($s as $tag) $area += $areas[$tag];
$r = max($r, $area);
}
}
}
return $r === 0 ? $n ** 2 : $r;
}
function dfs(&$grid, $n, $x, $y, &$tags, $tag, &$dr) {
$index = $x * $n + $y;
if ($tags[$index] > 0) return 0;
$tags[$index] = $tag;
$r = 1;
foreach ($dr as $d) {
$nx = $x + $d[0];
$ny = $y + $d[1];
if ($nx < 0 || $nx >= $n || $ny < 0 || $ny >= $n || $grid[$nx][$ny] === 0) continue;
$r += $this->dfs($grid, $n, $nx, $ny, $tags, $tag, $dr);
}
return $r;
}
}func largestIsland(grid [][]int) int {
n := len(grid)
r, tag, dr := 0, 1, []struct{dx, dy int}
tags, areas := make([]int, n * n), make([]int, n * n + 1)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
areas[tag] = dfs(grid, n, i, j, tags, tag, dr)
tag++
}
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 0 {
s := map[int]struct{}{}
for _, d := range dr {
nx, ny := i + d.dx, j + d.dy
if nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0 {
continue
}
s[tags[nx * n + ny]] = struct{}{}
}
area := 1
for tag, _ := range s {
area += areas[tag]
}
r = max(r, area)
}
}
}
if r == 0 {
return n * n
}
return r
}
func dfs(grid [][]int, n int, i int, j int, tags []int, tag int, dr []struct{dx, dy int}) int {
index, r := i * n + j, 1
if tags[index] > 0 {
return 0
}
tags[index] = tag
for _, d := range dr {
nx, ny := i + d.dx, j + d.dy
if nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0 {
continue
}
r += dfs(grid, n, nx, ny, tags, tag, dr)
}
return r
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length, tag = 1, r = 0;
int[] tags = new int[n * n], areas = new int[n * n + 1];
int[][] dr = ;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
areas[tag] = dfs(grid, n, i, j, tags, tag, dr);
tag++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
Set<Integer> s = new HashSet<Integer>();
for (int[] d : dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
s.add(tags[nx * n + ny]);
}
int area = 1;
for (int t : s) {
area += areas[t];
}
r = Math.max(r, area);
}
}
}
return r == 0 ? n * n : r;
}
public int dfs(int[][] grid, int n, int i, int j, int[] tags, int tag, int[][] dr) {
int index = i * n + j, r = 1;
if (tags[index] > 0) return 0;
tags[index] = tag;
for (int[] d : dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
r += dfs(grid, n, nx, ny, tags, tag, dr);
}
return r;
}
}public class Solution {
public int LargestIsland(int[][] grid) {
int n = grid.Length, tag = 1, r = 0;
int[] tags = new int[n * n + 1], areas = new int[n * n + 1];
int[][] dr = {new int[]{0, 1}, new int[]{1, 0}, new int[]{-1, 0}, new int[]{0, -1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
areas[tag] = dfs(grid, n, i, j, tags, tag, dr);
tag++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
ISet<int> s = new HashSet<int>();
foreach (int[] d in dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
s.Add(tags[nx * n + ny]);
}
int area = 1;
foreach (int t in s) {
area += areas[t];
}
r = Math.Max(r, area);
}
}
}
return r == 0 ? n * n : r;
}
public int dfs(int[][] grid, int n, int i, int j, int[] tags, int tag, int[][] dr) {
int index = i * n + j, r = 1;
if (tags[index] > 0) return 0;
tags[index] = tag;
foreach (int[] d in dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
r += dfs(grid, n, nx, ny, tags, tag, dr);
}
return r;
}
}#define MAX(a, b) (a > b ? a : b)
typedef struct {
int key;
UT_hash_handle hh;
} HashItem;
int dfs(int** grid, int gridSize, int i, int j, int* tags, int tag, const int* dr) {
int r = 1, index = i * gridSize + j;
if (tags[index] > 0) return 0;
tags[index] = tag;
for (int k = 0; k < 4; k++) {
int nx = i + dr[k], ny = j + dr[k + 1];
if (nx < 0 || nx >= gridSize || ny < 0 || ny >= gridSize || grid[nx][ny] == 0) continue;
r += dfs(grid, gridSize, nx, ny, tags, tag, dr);
}
return r;
}
int largestIsland(int** grid, int gridSize, int* gridColSize){
int r = 0, tag = 1;
int* tags = malloc(sizeof(int) * (gridSize * gridSize + 1));
int* areas = malloc(sizeof(int) * (gridSize * gridSize + 1));
const int dr[5] = {0, 1, 0, -1, 0};
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
if (grid[i][j] == 1) {
areas[tag] = dfs(grid, gridSize, i, j, tags, tag, dr);
tag++;
}
}
}
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
if (grid[i][j] == 0) {
HashItem* s = NULL;
for (int k = 0; k < 4; k++) {
int nx = i + dr[k], ny = j + dr[k + 1];
if (nx < 0 || nx >= gridSize || ny < 0 || ny >= gridSize || grid[nx][ny] == 0) continue;
HashItem* pEntry = NULL;
int t = tags[nx * gridSize + ny];
HASH_FIND_INT(s, &t, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = t;
HASH_ADD_INT(s, key, pEntry);
}
}
int area = 1;
HashItem* cur, *tmp;
HASH_ITER(hh, s, cur, tmp) {
area += areas[cur->key];
free(cur);
}
r = MAX(r, area);
}
}
}
free(tags);
free(areas);
return r == 0 ? gridSize * gridSize : r;
}class Solution {
public:
vector<vector<int>> dr = ;
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size(), tag = 1, r = 0;
vector<vector<int>> tags(n, vector<int>(n));
unordered_map<int, int> areas;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && tags[i][j] == 0) {
areas.emplace(tag, dfs(grid, n, i, j, tags, tag));
tag++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
unordered_set<int> s;
for (vector<int> d : dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
s.emplace(tags[nx][ny]);
}
int area = 1;
for (int tag : s) {
area += areas[tag];
}
r = max(r, area);
}
}
}
return r == 0 ? n * n : r;
}
int dfs(vector<vector<int>>& grid, int n, int i, int j, vector<vector<int>>& tags, int tag) {
int r = 1;
if (tags[i][j] > 0) return 0;
tags[i][j] = tag;
for (vector<int> d : dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
r += dfs(grid, n, nx, ny, tags, tag);
}
return r;
}
};class Solution:
dr = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def largestIsland(self, grid: List[List[int]]) -> int:
n, r, tag = len(grid), 0, 1
tags, areas = {}, [0] * (n * n + 1)
for i in range(0, n):
for j in range(0, n):
if grid[i][j] == 1:
areas[tag] = self.dfs(grid, n, i, j, tags, tag)
tag += 1
for i in range(0, n):
for j in range(0, n):
if grid[i][j] == 0:
s, area = set(), 1
for d in self.dr:
nx, ny = i + d[0], j + d[1]
if nx < 0 or nx >= n or ny < 0 or ny >=n or grid[nx][ny] == 0: continue
tag = tags[nx * n + ny]
if tag not in s:
s.add(tag)
area += areas[tag]
r = max(r, area)
return n * n if r == 0 else r
def dfs(self, grid: List[List[int]], n: int, i: int, j: int, tags: List[int], tag: int) -> int:
index, r = i * n + j, 1
if index in tags: return 0
tags[index] = tag
for d in self.dr:
nx, ny = i + d[0], j + d[1]
if nx < 0 or nx >= n or ny < 0 or ny >=n or grid[nx][ny] == 0: continue
r += self.dfs(grid, n, nx, ny, tags, tag)
return r标记 · 广度优先搜索
var largestIsland = function(grid) {
const n = grid.length, dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
const tags = new Uint32Array(n ** 2), areas = new Uint32Array(n ** 2)
let r = 0, tag = 1
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) areas[tag] = bfs(grid, n, i, j, tags, tag++, dr)
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) continue
const s = new Set
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
s.add(tags[nx * n + ny])
}
let area = 1
for (const tag of s) area += areas[tag]
r = Math.max(r, area)
}
}
return r === 0 ? n ** 2 : r
};
const bfs = (grid, n, x, y, tags, tag, dr) => {
let r = 0
const q = [[x, y]]
while (q.length) {
const [x, y] = q.shift(), index = x * n + y
if (tags[index] !== 0) continue
tags[index] = tag
r++
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
q.push([nx, ny])
}
}
return r
}function largestIsland(grid: number[][]): number {
const n = grid.length, dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
const tags = new Array(n ** 2).fill(0), areas = new Array(n ** 2)
let r = 0, tag = 1
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) areas[tag] = bfs(grid, n, i, j, tags, tag++, dr)
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) continue
const s = new Set<number>();
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
s.add(tags[nx * n + ny])
}
let area = 1
for (const tag of s) area += areas[tag]
r = Math.max(r, area)
}
}
return r === 0 ? n ** 2 : r
};
const bfs = (grid: number[][], n: number, x: number, y: number, tags: number[], tag: number, dr: number[][]): number => {
let r = 0
const q = [[x, y]]
while (q.length) {
const [x, y] = q.shift(), index = x * n + y
if (tags[index] !== 0) continue
tags[index] = tag
r++
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue
q.push([nx, ny])
}
}
return r
}class Solution {
function largestIsland($grid) {
$n = count($grid);
$tags = array_fill(0, $n * $n, 0);
$areas = array_fill(0, $n * $n, 0);
$r = 0;
$tag = 1;
$dr = [[0, 1], [1, 0], [0, -1], [-1, 0]];
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($grid[$i][$j] === 1) {
$areas[$tag] = $this->bfs($grid, $n, $i, $j, $tags, $tag, $dr);
$tag++;
}
}
}
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($grid[$i][$j] === 0) {
$s = array();
foreach ($dr as $d) {
$nx = $i + $d[0];
$ny = $j + $d[1];
if ($nx < 0 || $nx >= $n || $ny < 0 || $ny >= $n || $grid[$nx][$ny] === 0) continue;
if (in_array($tags[$nx * $n + $ny], $s) === false) $s []= $tags[$nx * $n + $ny];
}
$area = 1;
foreach ($s as $tag) $area += $areas[$tag];
$r = max($r, $area);
}
}
}
return $r === 0 ? $n ** 2 : $r;
}
function bfs(&$grid, $n, $x, $y, &$tags, $tag, &$dr) {
$q = [[$x, $y]];
$r = 0;
while (count($q) > 0) {
list($x, $y) = array_shift($q);
$index = $x * $n + $y;
if ($tags[$index] > 0) continue;
$tags[$index] = $tag;
$r++;
foreach ($dr as $d) {
$nx = $x + $d[0];
$ny = $y + $d[1];
if ($nx < 0 || $nx >= $n || $ny < 0 || $ny >= $n || $grid[$nx][$ny] === 0) continue;
$q []= [$nx, $ny];
}
}
return $r;
}
}func largestIsland(grid [][]int) int {
n := len(grid)
r, tag, dr := 0, 1, []struct{dx, dy int}
tags, areas := make([]int, n * n), make([]int, n * n + 1)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
areas[tag] = bfs(grid, n, i, j, tags, tag, dr)
tag++
}
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 0 {
s := map[int]struct{}{}
for _, d := range dr {
nx, ny := i + d.dx, j + d.dy
if nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0 {
continue
}
s[tags[nx * n + ny]] = struct{}{}
}
area := 1
for tag, _ := range s {
area += areas[tag]
}
r = max(r, area)
}
}
}
if r == 0 {
return n * n
}
return r
}
func bfs(grid [][]int, n int, i int, j int, tags []int, tag int, dr []struct{dx, dy int}) int {
q, r := [][]int, 0
for len(q) > 0 {
x, y := q[0][0], q[0][1]
q = q[1:]
index := x * n + y
if tags[index] > 0 {
continue
}
tags[index] = tag
r++
for _, d := range dr {
nx, ny := x + d.dx, y + d.dy
if nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0 {
continue
}
q = append(q, []int{nx, ny})
}
}
return r
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length, tag = 1, r = 0;
int[] tags = new int[n * n], areas = new int[n * n + 1];
int[][] dr = ;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
areas[tag] = bfs(grid, n, i, j, tags, tag, dr);
tag++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
Set<Integer> s = new HashSet<Integer>();
for (int[] d : dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
s.add(tags[nx * n + ny]);
}
int area = 1;
for (int t : s) {
area += areas[t];
}
r = Math.max(r, area);
}
}
}
return r == 0 ? n * n : r;
}
public int bfs(int[][] grid, int n, int i, int j, int[] tags, int tag, int[][] dr) {
int r = 0;
Deque<int[]> q = new ArrayDeque<int[]>();
q.offerLast(new int[]{i, j});
while (q.isEmpty() == false) {
int[] t = q.pollFirst();
int x = t[0], y = t[1];
int index = x * n + y;
if (tags[index] > 0) continue;
tags[index] = tag;
r++;
for (int[] d : dr) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
q.offerLast(new int[]{nx, ny});
}
}
return r;
}
}public class Solution {
public int LargestIsland(int[][] grid) {
int n = grid.Length, tag = 1, r = 0;
int[] tags = new int[n * n + 1], areas = new int[n * n + 1];
int[][] dr = {new int[]{0, 1}, new int[]{1, 0}, new int[]{-1, 0}, new int[]{0, -1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
areas[tag] = bfs(grid, n, i, j, tags, tag, dr);
tag++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
ISet<int> s = new HashSet<int>();
foreach (int[] d in dr) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
s.Add(tags[nx * n + ny]);
}
int area = 1;
foreach (int t in s) {
area += areas[t];
}
r = Math.Max(r, area);
}
}
}
return r == 0 ? n * n : r;
}
public int bfs(int[][] grid, int n, int i, int j, int[] tags, int tag, int[][] dr) {
Queue<int[]> q = new Queue<int[]>();
q.Enqueue(new int[]{i, j});
int r = 0;
while (q.Count > 0) {
int[] t = q.Dequeue();
int x = t[0], y = t[1];
int index = x * n + y;
if (tags[index] > 0) continue;
tags[index] = tag;
r++;
foreach (int[] d in dr) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 0) continue;
q.Enqueue(new int[]{nx, ny});
}
}
return r;
}
}#define MAX(a, b) (a > b ? a : b)
typedef struct {
int key;
UT_hash_handle hh;
} HashItem;
typedef struct {
int x;
int y;
} Points;
int bfs(int** grid, int gridSize, int i, int j, int* tags, int tag, const int* dr) {
Points** q = malloc(sizeof(Points*) * (500 * 500));
Points* pEntry = malloc(sizeof(Points));
pEntry->x = i;
pEntry->y = j;
int start = 0, end = 1, r =0;
q[start] = pEntry;
while (start < end) {
Points* t = q[start++];
int x = t->x, y = t->y;
free(t);
int index = x * gridSize + y;
if (tags[index] > 0) continue;
tags[index] = tag;
r++;
for (int k = 0; k < 4; k++) {
int nx = x + dr[k], ny = y + dr[k + 1];
if (nx < 0 || nx >= gridSize || ny < 0 || ny >= gridSize || grid[nx][ny] == 0) continue;
pEntry = malloc(sizeof(Points));
pEntry->x = nx;
pEntry->y = ny;
q[end++] = pEntry;
}
}
return r;
}
int largestIsland(int** grid, int gridSize, int* gridColSize){
int r = 0, tag = 1;
int* tags = malloc(sizeof(int) * (gridSize * gridSize + 1));
int* areas = malloc(sizeof(int) * (gridSize * gridSize + 1));
const int dr[5] = {0, 1, 0, -1, 0};
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
if (grid[i][j] == 1) {
if (tags[i * gridSize + j] > 0) continue;
areas[tag] = bfs(grid, gridSize, i, j, tags, tag, dr);
tag++;
}
}
}
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
if (grid[i][j] == 0) {
HashItem* s = NULL;
for (int k = 0; k < 4; k++) {
int nx = i + dr[k], ny = j + dr[k + 1];
if (nx < 0 || nx >= gridSize || ny < 0 || ny >= gridSize || grid[nx][ny] == 0) continue;
HashItem* pEntry = NULL;
int t = tags[nx * gridSize + ny];
HASH_FIND_INT(s, &t, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = t;
HASH_ADD_INT(s, key, pEntry);
}
}
int area = 1;
HashItem* cur, *tmp;
HASH_ITER(hh, s, cur, tmp) {
area += areas[cur->key];
free(cur);
}
r = MAX(r, area);
}
}
}
free(tags);
free(areas);
return r == 0 ? gridSize * gridSize : r;
}class Solution:
dr = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def largestIsland(self, grid: List[List[int]]) -> int:
n, r, tag = len(grid), 0, 1
tags, areas = {}, [0] * (n * n + 1)
for i in range(0, n):
for j in range(0, n):
if grid[i][j] == 1:
areas[tag] = self.bfs(grid, n, i, j, tags, tag)
tag += 1
for i in range(0, n):
for j in range(0, n):
if grid[i][j] == 0:
s, area = set(), 1
for d in self.dr:
nx, ny = i + d[0], j + d[1]
if nx < 0 or nx >= n or ny < 0 or ny >=n or grid[nx][ny] == 0: continue
tag = tags[nx * n + ny]
if tag not in s:
s.add(tag)
area += areas[tag]
r = max(r, area)
return n * n if r == 0 else r
def bfs(self, grid: List[List[int]], n: int, i: int, j: int, tags: List[int], tag: int) -> int:
r = 0
q = [[i, j]]
while len(q):
x, y = q.pop()
index = x * n + y
if index in tags: continue
tags[index] = tag
r += 1
for d in self.dr:
nx, ny = x + d[0], y + d[1]
if nx < 0 or nx >= n or ny < 0 or ny >=n or grid[nx][ny] == 0: continue
q.append([nx, ny])
return r并查集 · 深度优先搜索
var largestIsland = function(grid) {
const m = grid.length, n = grid[0].length, u = new UnionFind(m * n), visited = new Uint8Array(m * n)
const dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
let r = 0
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) dfs(grid, m, n, i, j, u, visited, dr)
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
const s = new Set
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
s.add(u.find(nx * m + ny))
}
let area = 1
for (const index of s) {
area += u.size(index)
}
r = Math.max(r, area)
}
}
}
return r === 0 ? m * n : r
};
const dfs = (grid, m, n, x, y, u, visited, dr) => {
const index = x * m + y
if (visited[index] === 1) return
visited[index] = 1
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
u.union(index, nx * m + ny)
dfs(grid, m, n, nx, ny, u, visited, dr)
}
}
class UnionFind {
constructor(n) {
this.parents = new Uint32Array(n)
this.sizes = new Array(n).fill(1)
while (n--) this.parents[n] = n
}
union(x, y) {
const rootX = this.find(x), rootY = this.find(y)
if (rootX === rootY) return
if (this.sizes[rootX] >= this.sizes[rootY]) {
this.parents[rootY] = rootX
this.sizes[rootX] += this.sizes[rootY]
} else {
this.parents[rootX] = rootY
this.sizes[rootY] += this.sizes[rootX]
}
}
find(x) {
while (x !== this.parents[x]) x = this.parents[this.parents[x]]
return x
}
size(x) {
return this.sizes[this.find(x)]
}
}function largestIsland(grid: number[][]): number {
const n = grid.length, u = new UnionFind(n * n), visited = new Array(n * n).fill(0)
const dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
let r = 0
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) dfs(grid, n, i, j, u, visited, dr)
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
const s = new Set
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
s.add(u.find(nx * n + ny))
}
let area = 1
for (const index of s) {
area += u.size(index)
}
r = Math.max(r, area)
}
}
}
return r === 0 ? n * n : r
};
const dfs = (grid: number[][], n: number, x: number, y: number, u: UnionFind, visited: number[], dr: number[][]) => {
const index = x * n + y
if (visited[index] === 1) return
visited[index] = 1
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
u.union(index, nx * n + ny)
dfs(grid, n, nx, ny, u, visited, dr)
}
}
class UnionFind {
#parents: number[]
#sizes: number[]
constructor(n) {
this.#parents = new Array(n)
this.#sizes = new Array(n).fill(1)
while (n--) this.#parents[n] = n
}
union(x, y) {
const rootX = this.find(x), rootY = this.find(y)
if (rootX === rootY) return
if (this.#sizes[rootX] >= this.#sizes[rootY]) {
this.#parents[rootY] = rootX
this.#sizes[rootX] += this.#sizes[rootY]
} else {
this.#parents[rootX] = rootY
this.#sizes[rootY] += this.#sizes[rootX]
}
}
find(x) {
while (x !== this.#parents[x]) x = this.parents[x]]
return x
}
size(x) {
return this.#sizes[this.find(x)]
}
}并查集 · 广度优先搜索
var largestIsland = function(grid) {
const m = grid.length, n = grid[0].length, u = new UnionFind(m * n), visited = new Uint8Array(m * n)
const dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
let r = 0
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) bfs(grid, m, n, i, j, u, visited, dr)
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
const s = new Set
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
s.add(u.find(nx * m + ny))
}
let area = 1
for (const index of s) {
area += u.size(index)
}
r = Math.max(r, area)
}
}
}
return r === 0 ? m * n : r
};
const bfs = (grid, m, n, i, j, u, visited, dr) => {
const q = [[i, j]]
while (q.length) {
const [x, y] = q.shift()
const index = x * m + y
if (visited[index] === 1) continue
visited[index] = 1
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
u.union(index, nx * m + ny)
q.push([nx, ny])
}
}
}
class UnionFind {
constructor(n) {
this.parents = new Uint32Array(n)
this.sizes = new Array(n).fill(1)
while (n--) this.parents[n] = n
}
union(x, y) {
const rootX = this.find(x), rootY = this.find(y)
if (rootX === rootY) return
if (this.sizes[rootX] >= this.sizes[rootY]) {
this.parents[rootY] = rootX
this.sizes[rootX] += this.sizes[rootY]
} else {
this.parents[rootX] = rootY
this.sizes[rootY] += this.sizes[rootX]
}
}
find(x) {
while (x !== this.parents[x]) x = this.parents[this.parents[x]]
return x
}
size(x) {
return this.sizes[this.find(x)]
}
}function largestIsland(grid: number[][]): number {
const n = grid.length, u = new UnionFind(n * n), visited = new Array(n * n).fill(0)
const dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
let r = 0
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) bfs(grid, n, i, j, u, visited, dr)
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
const s = new Set
for (const d of dr) {
const nx = i + d[0], ny = j + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
s.add(u.find(nx * n + ny))
}
let area = 1
for (const index of s) {
area += u.size(index)
}
r = Math.max(r, area)
}
}
}
return r === 0 ? n * n : r
};
const bfs = (grid: number[][], n: number, x: number, y: number, u: UnionFind, visited: number[], dr: number[][]) => {
const q = [[x, y]]
while (q.length) {
const [x, y] = q.shift()
const index = x * n + y
if (visited[index] === 1) continue
visited[index] = 1
for (const d of dr) {
const nx = x + d[0], ny = y + d[1]
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
if (grid[nx][ny] === 0) continue
u.union(index, nx * n + ny)
q.push([nx, ny])
}
}
}
class UnionFind {
#parents: number[]
#sizes: number[]
constructor(n) {
this.#parents = new Array(n)
this.#sizes = new Array(n).fill(1)
while (n--) this.#parents[n] = n
}
union(x, y) {
const rootX = this.find(x), rootY = this.find(y)
if (rootX === rootY) return
if (this.#sizes[rootX] >= this.#sizes[rootY]) {
this.#parents[rootY] = rootX
this.#sizes[rootX] += this.#sizes[rootY]
} else {
this.#parents[rootX] = rootY
this.#sizes[rootY] += this.#sizes[rootX]
}
}
find(x) {
while (x !== this.#parents[x]) x = this.parents[x]]
return x
}
size(x) {
return this.#sizes[this.find(x)]
}
}