这题复用了word serach的很多代码 , 还把问题降级到找出从某个点开始能floodfill到的格子数 , 一次过了
findCloseGrids(grid,srow,scol) {
if grid[srow][scol]!=1 {
return 0
}
res=1
mark [srow,scol] as visited
access in up down right left order
if [nrow,ncol] not visited and inarea
res+=findCloseGrids(grid,nrow,ncol)
return res
}
type Solution struct {
visited map[int]map[int]bool
}
func (t *Solution) findCloseGrids(grid [][]byte , srow int,scol int) int {
if grid[srow][scol]!='1' {
return 0
}
res:=1
if _,ok:=t.visited[srow];!ok {
t.visited[srow] = make(map[int]bool)
}
t.visited[srow][scol] = true
coord := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} //up right down left
for _, v := range coord {
nrow := srow + v[0]
ncol := scol + v[1]
if inArea(ncol, nrow, grid) && !t._visited(ncol, nrow) {
res += t.findCloseGrids(grid,nrow,ncol)
}
}
return res
}
func (t *Solution) _visited(col int, row int) bool {
if _, ok := t.visited[row][col]; ok {
return true
} else {
return false
}
}
func inArea(col int, row int, board [][]byte) bool {
return row >= 0 && row <= len(board)-1 && col >= 0 && col <= len(board[0])-1
}
func numIslands(grid [][]byte) int {
s := Solution{visited: make(map[int]map[int]bool)}
res:=0
for row, rowdata := range grid {
for col, _ := range rowdata {
if !s._visited(col,row) {
if s.findCloseGrids(grid,row,col)>0{
res+=1
}
}
}
}
return res
}
