Re: [閒聊] 每日leetcode
827. Making A Large Island
思路:
先用bfs把每個島嶼都表示出來
並且記錄每個島嶼的面積
接著對每個grid[i][j] == 0的點
去看如果這個點變成陸地，往4個方向去找有沒有其他島嶼
看最大的陸地面積會是多大
golang code:
var n, m int
func largestIsland(grid [][]int) int {
n, m = len(grid), len(grid[0])
ans := 0
island, islandNum, area := make([][]int, n), 1, []int{0, 0}
direction := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for key := range grid {
island[key] = make([]int, m)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 1 && island[i][j] == 0 {
area[islandNum] = bfs(i, j, island, islandNum, grid)
ans = max(ans, area[islandNum])
islandNum++
area = append(area, 0)
}
}
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 0 {
tmp, visited := 1, make(map[int]bool)
for k := 0; k < 4; k++ {
next_i, next_j := i+direction[k][0], j+direction[k][1]
if next_i > -1 && next_j > -1 && next_i < n && next_j < m {
if !visited[island[next_i][next_j]] {
visited[island[next_i][next_j]] = true
tmp += area[island[next_i][next_j]]
}
}
}
ans = max(ans, tmp)
}
}
}
return ans
}
func bfs(i, j int, island [][]int, islandNum int, grid [][]int) int {
direction := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
island[i][j] = islandNum
res := 1
for _, val := range direction {
next_i, next_j := i+val[0], j+val[1]
if next_i > -1 && next_j > -1 && next_i < n && next_j < m && island[next_i][
next_j] == 0 && grid[next_i][next_j] == 1 {
res += bfs(next_i, next_j, island, islandNum, grid)
}
}
return res
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.38.32 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1738323894.A.AE2.html
推
01/31 19:46,
10月前
, 1F
01/31 19:46, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1316 之 1552 篇)：