63 lines
1.6 KiB
Go
63 lines
1.6 KiB
Go
package top100liked
|
|
|
|
import (
|
|
"fmt"
|
|
"testing"
|
|
)
|
|
|
|
// https://leetcode.cn/problems/number-of-islands/?envType=study-plan-v2&envId=top-100-liked
|
|
|
|
func numIslands(grid [][]byte) int {
|
|
m := len(grid)
|
|
n := len(grid[0])
|
|
visited := make([][]bool, m)
|
|
for i := range m {
|
|
visited[i] = make([]bool, n)
|
|
}
|
|
res := 0
|
|
type point struct {
|
|
Row int
|
|
Column int
|
|
}
|
|
queue := []point{}
|
|
for i := range m {
|
|
for j := range n {
|
|
if !visited[i][j] && grid[i][j] == '1' {
|
|
queue = append(queue, point{i, j})
|
|
visited[i][j] = true
|
|
res++
|
|
}
|
|
for len(queue) > 0 {
|
|
cur := queue[0]
|
|
queue = queue[1:]
|
|
// 左侧
|
|
if cur.Column > 0 && !visited[cur.Row][cur.Column-1] && grid[cur.Row][cur.Column-1] == '1' {
|
|
queue = append(queue, point{cur.Row, cur.Column - 1})
|
|
visited[cur.Row][cur.Column-1] = true
|
|
}
|
|
// 右侧
|
|
if cur.Column+1 < n && !visited[cur.Row][cur.Column+1] && grid[cur.Row][cur.Column+1] == '1' {
|
|
queue = append(queue, point{cur.Row, cur.Column + 1})
|
|
visited[cur.Row][cur.Column+1] = true
|
|
}
|
|
// 上侧
|
|
if cur.Row > 0 && !visited[cur.Row-1][cur.Column] && grid[cur.Row-1][cur.Column] == '1' {
|
|
queue = append(queue, point{cur.Row - 1, cur.Column})
|
|
visited[cur.Row-1][cur.Column] = true
|
|
}
|
|
// 下侧
|
|
if cur.Row+1 < m && !visited[cur.Row+1][cur.Column] && grid[cur.Row+1][cur.Column] == '1' {
|
|
queue = append(queue, point{cur.Row + 1, cur.Column})
|
|
visited[cur.Row+1][cur.Column] = true
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return res
|
|
}
|
|
|
|
func Test(t *testing.T) {
|
|
input := [][]byte{{'1', '1', '1'}, {'0', '1', '0'}, {'1', '1', '1'}}
|
|
fmt.Println(numIslands(input))
|
|
}
|