題目連接

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

題目描述

給定一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格重慢，計(jì)算島嶼的數(shù)量。一個(gè)島被水包圍肄梨，并且它是通過(guò)水平方向或垂直方向上相鄰的陸地連接而成的欧啤。你可以假設(shè)網(wǎng)格的四個(gè)邊均被水包圍断凶。

示例 1:

輸入:
11110
11010
11000
00000

輸出: 1
示例 2:

輸入:
11000
11000
00100
00011

輸出: 3

go語(yǔ)言題解

深度優(yōu)先搜索

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])
    //標(biāo)記visited
    grid[r][c] = 48

    //如果有下一個(gè)節(jié)點(diǎn)，并且節(jié)點(diǎn)沒(méi)有被訪問(wèn)過(guò)，就深搜下一個(gè)節(jié)點(diǎn)
    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)
    } 

}

廣度優(yōu)先搜索

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 , 又沒(méi)有被訪問(wèn), 加入隊(duì)列 
            if grid[r][c] == 49{
                //標(biāo)記visited
                grid[r][c] = 48
                queue = append(queue, rc{r, c})

                num ++
                //隊(duì)列沒(méi)有空說(shuō)明還有島嶼連接缅茉，可以繼續(xù)搜下一層
                //如果隊(duì)列為空了凤巨，說(shuō)明這個(gè)島嶼也到了邊界了视乐，退出循環(huán)，開(kāi)始搜下一個(gè)島嶼
                for len(queue) != 0{
                    q := queue[0]
                    queue = queue[1:]  //pop )
                
                   //搜索下一層敢茁，如果有沒(méi)有被訪問(wèn)過(guò)并值為1的炊林，則繼續(xù)加入隊(duì)列中
                    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
    
}