网站排名优化公司哪家好_中国电信六大外包公司_友情下载网站_宁波seo快速优化

【LeetCode】827、最大人工岛

一、洪水填充DFS

1.1 洪水填充DFS

原 grid 可以分为不同的 岛屿, 为了区分, 可以给每个岛一个 id, 比如有 id 为1 的岛, id 为 2 的岛, …
每个格子要么是 “陆地”, 要么是 “水”
最终遍历每个 “水”, 看若其变为 “陆地”, 其上下左右四个格子可以连通多大的岛屿

其中, 注意, 可能上下左右有重复的岛屿, 需去重. 比如 左测, 下方, 右侧都是 id 为 5 的岛屿, 则需去重.

• 若都是不同 id 的岛屿, 则岛屿面积为 各侧岛屿面积之和, 因为各侧岛屿被这个格子连起来了
• 若都是相同 id 的岛屿, 则岛屿面积+1, 因为加的就是这个格子

// go
func largestIsland(g [][]int) int {id := 2 // 岛屿id从2开始, 因为图中已有0和1了n := len(g)var dfs func (i,j,id int) // 从g[i][j]格子 开始标记为 第id编号的岛屿dfs = func(i,j,id int) {if i < 0 || i == n || j < 0 || j == n || g[i][j] != 1 {return}g[i][j] = iddfs(i-1,j,id); dfs(i+1,j,id); dfs(i,j-1,id); dfs(i,j+1,id)}for i := range n { // 给岛屿编号for j := range n {if g[i][j] == 1 {dfs(i,j,id); id++}}}size := make([]int, id) // 各id岛屿的面积ans := 0 // 因为即使没有任何水变陆地, 原有的岛屿面积也可以的, 所以求原各岛屿最大的面积作为初值, 后续若水变陆地成功连接后可再更新ansfor i := range n {for j := range n {if id := g[i][j]; id > 1 { // id > 1 才是岛屿, PS此时已没有id为1的了, 只有0和>1的size[id]++ // 更新 size[]ans = max(ans, size[id]) // 更新 ans}}}visited := make([]bool, id) // 上下左右的去重var up, down, left, right, merge intfor i := range n { // 看水变为陆地后, 能否增加面积for j := range n {if g[i][j] != 0 {continue} // 只看 水if i > 0 { up = g[i-1][j] } else { up = 0 } // size[0] 是 0if i+1 < n { down = g[i+1][j] } else { down = 0 }if j > 0 { left = g[i][j-1] } else { left = 0 }if j+1 < n { right = g[i][j+1] } else { right = 0 }visited[up] = truemerge = 1 + size[up]if !visited[down] {merge += size[down]visited[down] = true}if !visited[left] {merge += size[left]visited[left] = true}if !visited[right] {merge += size[right]visited[right] = true}ans = max(ans, merge)visited[up] = falsevisited[down] = falsevisited[left] = falsevisited[right] = false}}return ans
}

参考
参考

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts