[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
3
[[0]]
0
[[1,1],[1,1]]
1
01矩阵范围<=200*200
type UnionFind struct {
fx []int
count int
}
func (uf *UnionFind) init(grid [][]byte) {
m := len(grid)
n := len(grid[0])
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
uf.count++
uf.fx = append(uf.fx, i*n+j)
} else {
uf.fx = append(uf.fx, -1)
}
}
}
}
func (uf *UnionFind) find(x int) int {
if uf.fx[x] != x {
uf.fx[x] = uf.find(uf.fx[x])
return uf.fx[x]
}
return x
}
func (uf *UnionFind) union(a, b int) {
x := uf.find(a)
y := uf.find(b)
if x != y {
uf.fx[x] = y
uf.count--
}
}
func solve( grid [][]byte ) int {
// write code here
m := len(grid)
n := len(grid[0])
if m == 0 {
return 0
}
uf := new(UnionFind)
uf.init(grid)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
if i-1 >= 0 && grid[i-1][j] == '1' {
uf.union(i*n+j, (i-1)*n+j)
}
if i+1 < m && grid[i+1][j] == '1' {
uf.union(i*n+j, (i+1)*n+j)
}
if j-1 >= 0 && grid[i][j-1] == '1' {
uf.union(i*n+j, i*n+j-1)
}
if j+1 < n && grid[i][j+1] == '1' {
uf.union(i*n+j, i*n+j+1)
}
}
}
}
return uf.count
} 
func solve( grid [][]byte ) int {
// 用一个辅助表格visited记录遍历过的点
// 双层遍历走每个点，命中陆地则计数，并上下左右的dfs探索标记为已探索（同一陆地）的
if len(grid) == 0 {
return 0
}
m, n := len(grid), len(grid[0])
visited := make([][]bool, m)
for i := range visited {
visited[i] = make([]bool, n)
}
count := 0
var dfs func(i, j int)
dfs = func(i, j int) {
//退出条件：1.边界，2，访问过，3，海水
if i < 0 || i >= m || j < 0 || j >= n || visited[i][j]|| grid[i][j] == '0'{
return
}
visited[i][j] = true
disc := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
for _, d := range disc {
raw := i+d[0]
col := j+d[1]
dfs(raw, col)
}
}
for i := 0; i<m; i++ {
for j := 0; j< n; j++ { // 找到一个点将这个点所有的都标记为访问过，且内容为0
if !visited[i][j] && grid[i][j] == '1'{
dfs(i, j)
count++
}
}
}
return count
} func solve( grid [][]byte ) (sum int) {
row, col, sum := len(grid), len(grid[0]), 0
var dfs func(int, int)
dfs = func(x, y int) {
if x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == '0' {
return
}
grid[x][y]= '0'
dfs(x+1, y)
dfs(x, y+1)
dfs(x-1, y)
dfs(x, y-1)
}
for x:=0; x<row; x++ {
for y:=0; y<col; y++ {
if grid[x][y] == '1' {
dfs(x, y)
sum++
}
}
}
return
} 
package main
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
func solve( grid [][]byte ) int {
// write code here
var res int
long := len(grid)
if long == 0 {
return res
}
m := len(grid)
n := len(grid[0])
visited := make([][]bool, m)
for loop := range visited{
visited[loop] = make([]bool, n)
}
for i := 0; i < m; i++{
for j:=0; j < n; j++{
if grid[i][j] == '1' && ! visited[i][j]{
bfs(grid, i, j, m, n, visited)
res ++
}
}
}
return res
}
func bfs(grid [][]byte, i, j, m, n int, visited [][]bool ) {
dics := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
visited[i][j] = true
quene := make([][]int, 0)
quene = append(quene, []int{i, j})
for len(quene) > 0 {
curX := quene[0][0]
curY := quene[0][1]
for _, dic := range dics{
X := curX + dic[0]
Y := curY + dic[1]
if isArea(X, Y, m, n) && grid[X][Y]== '1' && !visited[X][Y]{
quene = append(quene, []int{X,Y})
visited[X][Y] = true
}
}
quene = quene[1:]
}
}
func isArea(i, j, m, n int )bool {
return i >=0 && i< m && j >=0 && j< n
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
