200. Number of Islands

题目

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

题意

给定一个矩阵，1代表土地，0代表海洋，求出有一共有多少座岛屿。岛屿的四周必须都是水，假设矩阵外面全是水。

例子

Input:

11000
11000
00100
00011

Output: 3

解法

深度遍历并标记，遇到是1且还没标记的，标记该位并上下左右递归。类似图中搜索寻找有多少个连通图。最外层循环每一位，返回true则岛屿数量+1;

代码

var mark [][]bool
var R,L int
func numIslands(grid [][]byte) int {
    R = len(grid)
    if R==0{
        return 0
    }
    L = len(grid[0])
    if L==0{
        return 0
    }
    mark = make([][]bool,R)
    for i:=0;i<R;i++{
        mark[i]=make([]bool,L)
    }
    count := 0
    for i:=0;i<R;i++{
        for j:=0;j<L;j++{
            if SearchLand(grid,i,j){
              count++  
            }
        }
    }
    
    return count
}

func SearchLand(grid [][]byte,i,j int)bool{
    if i>=R || j>=L{
        return false
    }
    if i<0 || j<0{
        return false
    }
    
    if grid[i][j]=='0'{
        return false
    }
    if mark[i][j]{
        return false
    }

    mark[i][j]=true
    SearchLand(grid,i+1,j)
    SearchLand(grid,i,j+1)
    SearchLand(grid,i-1,j)
    SearchLand(grid,i,j-1)
    return true
}

总结

题目不难，总结就是递归遍历+标记，想到以前求非连通图的思路，跟这道题类似。一开始以为只要往右下方向遍历就好了，这点还是考虑不够周全。题目参数没看仔细，以为矩阵式int，结果细看是byte，导致浪费了点时间在找bug。