WechatIMG580.jpeg

題目描述

leetcode 第200題：島嶼數(shù)量
給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。
示例 1：
輸入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
輸出：1

解題方法

DFS
參照題解

• 解題思路

題中的島嶼grid是由二維網(wǎng)格組成的，也就是二維矩陣
首先獲取grid的行數(shù)m和列數(shù)n
定義變量num，存儲(chǔ)島嶼數(shù)量，初始為0
在[0,m)和[0,n)區(qū)間內(nèi)嵌套遍歷grid
如果當(dāng)前位置grid[i][j]是土地，num累加1，然后以當(dāng)前位置開(kāi)始進(jìn)行DFS
在DFS過(guò)程中，將訪問(wèn)過(guò)的土地標(biāo)為0，再對(duì)其上下左右的位置進(jìn)行DFS，直至訪問(wèn)不到土地
最后的島嶼數(shù)量就是num

• 復(fù)雜度

時(shí)間復(fù)雜度：O(mn)，m和n分別為島嶼grid的行數(shù)和列數(shù)。
空間復(fù)雜度：O(mn)

• 代碼實(shí)現(xiàn)

python3

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(cur_x,cur_y):
            grid[cur_x][cur_y] = 0
            for i,j in [[-1,0],[1,0],[0,-1],[0,1]]:
                next_x,next_y = cur_x+i,cur_y+j
                if 0<=next_x<m and 0<=next_y<n and grid[next_x][next_y]=="1":
                    dfs(next_x,next_y)
        m,n = len(grid),len(grid[0])
        num = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]=="1":
                    num += 1
                    dfs(i,j)
        return num

php

class Solution {
    function numIslands($grid) {
        $this->grid = $grid;
        $this->m = count($this->grid);
        $this->n = count($this->grid[0]);
        $num = 0;
        for($i=0;$i<$this->m;$i++){
            for($j=0;$j<$this->n;$j++){
                if($this->grid[$i][$j]=="1"){
                    $num++;
                    $this->dfs($i,$j);
                }
            }
        }
        return $num;
    }

    function dfs($cur_x,$cur_y){
        $this->grid[$cur_x][$cur_y] = 0;
        foreach([[-1,0],[1,0],[0,-1],[0,1]] as [$i,$j]){
            $next_x = $cur_x+$i;
            $next_y = $cur_y+$j;
            if(0<=$next_x && $next_x<$this->m && 0<=$next_y && $next_y<$this->n && $this->grid[$next_x][$next_y]=="1"){
                $this->dfs($next_x,$next_y);
            }
        }
    }
}