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
}

大师