题目连接

https://leetcode-cn.com/problems/number-of-islands/

题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

go语言题解

深度优先搜索

func numIslands(grid [][]byte) int {
    rowsize := len(grid)
    if rowsize <= 0{
        return 0
    }
    colsize := len(grid[0])

    num := 0
    for i:=0; i<rowsize; i++{
        for j:=0; j<colsize; j++{
            if grid[i][j] == 49{
                num++
                dfs(grid, i, j)
            }
        }
    }
    return num
    
}

func dfs(grid[][] byte, r int, c int) {
    rowsize := len(grid)
    colsize := len(grid[0])
    //标记visited
    grid[r][c] = 48

    //如果有下一个节点，并且节点没有被访问过，就深搜下一个节点
    if r - 1 >= 0 && grid[r-1][c] == 49{
        dfs(grid, r-1, c)
    }
    if r + 1 < rowsize && grid[r+1][c] == 49{
        dfs(grid, r+1, c)
    } 
    if c - 1 >= 0 && grid[r][c-1] == 49{
        dfs(grid, r, c-1)
    }
    if c + 1 < colsize && grid[r][c+1] == 49{
        dfs(grid, r, c+1)
    } 

}

广度优先搜索

func bfs(grid[][] byte) int{
    rowsize := len(grid)
    if rowsize <= 0{
        return 0
    }
    colsize := len(grid[0])

    num := 0
    queue := make([]rc,0)

    
    for r:=0; r<rowsize; r++{
        for c:=0; c<colsize; c++{
            //如果为 1 , 又没有被访问, 加入队列 
            if grid[r][c] == 49{
                //标记visited
                grid[r][c] = 48
                queue = append(queue, rc{r, c})

                num ++
                //队列没有空说明还有岛屿连接，可以继续搜下一层
                //如果队列为空了，说明这个岛屿也到了边界了，退出循环，开始搜下一个岛屿
                for len(queue) != 0{
                    q := queue[0]
                    queue = queue[1:]  //pop )
                
                   //搜索下一层，如果有没有被访问过并值为1的，则继续加入队列中
                    if q.r+1 < rowsize && grid[q.r+1][q.c] == 49{
                        grid[q.r+1][q.c] = 48
                        queue = append(queue, rc{q.r+1, q.c})
                    }
                    if q.r-1 >= 0 && grid[q.r-1][q.c] == 49{
                        grid[q.r-1][q.c] = 48
                        queue = append(queue, rc{q.r-1, q.c})
                    }
                    if q.c+1 < colsize && grid[q.r][q.c+1] == 49{
                        grid[q.r][q.c+1] = 48
                        queue = append(queue, rc{q.r, q.c+1})
                    }
                    if q.c-1 >=0 && grid[q.r][q.c-1] == 49{
                        grid[q.r][q.c-1] = 48
                        queue = append(queue, rc{q.r, q.c-1})
                    }
                    

                }
            }
        }
    }
    return num
    
}