題目描述：

給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網(wǎng)格，請你計算網(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
示例 2：

輸入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
輸出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值為 ‘0’ 或 ‘1’

解題思路一：bfs，主要思想都是遇到一個沒有visited過的"陸地"先result += 1，然后用深搜或者廣搜將這片"陸地"全部做上visited標(biāo)記。

class Solution:
    def __init__(self):
        self.dirs = [(-1,0), (0, 1), (1, 0), (0, -1)] # 左上右下
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        result = 0
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == '1':
                    result += 1
                    self.bfs(grid, i, j, visited)
        return result

    def bfs(self, grid, x, y, visited):
        q = deque()
        q.append((x, y))
        visited[x][y] = True
        while q:
            x, y = q.popleft()
            for d in self.dirs:
                nextx = x + d[0]
                nexty = y + d[1]
                if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                    continue
                if not visited[nextx][nexty] and grid[nextx][nexty] == '1':
                    q.append((nextx, nexty))
                    visited[nextx][nexty] = True

時間復(fù)雜度：O(nm)
空間復(fù)雜度：O(nm)

解題思路二：dfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        dirs = [(-1,0), (0, 1), (1, 0), (0, -1)] # 左上右下
        result = 0
        def dfs(x, y):
            for d in dirs:
                nextx = x + d[0]
                nexty = y + d[1]
                if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:
                    continue
                if not visited[nextx][nexty] and grid[nextx][nexty] == '1':
                    visited[nextx][nexty] = True
                    dfs(nextx, nexty)

        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == '1':
                    visited[i][j] = True
                    result += 1
                    dfs(i, j)
        return result

時間復(fù)雜度：O(nm)
空間復(fù)雜度：O(nm)

解題思路三：并查集

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        f = {}

        def find(x):
            f.setdefault(x, x)
            if f[x] != x:
                f[x] = find(f[x])
            return f[x]

        def union(x, y):
            f[find(x)] = find(y)

        if not grid: return 0
        row = len(grid)
        col = len(grid[0])

        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    for x, y in [[-1, 0], [0, -1]]:
                        tmp_i = i + x
                        tmp_j = j + y
                        if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
                            union(tmp_i * row + tmp_j, i * row + j)
        # print(f)
        res = set()
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    res.add(find((i * row + j)))
        return len(res)

時間復(fù)雜度：O(mn)
空間復(fù)雜度：O(nm)文章來源地址http://www.zghlxwxcb.cn/news/detail-850979.html

到了這里，關(guān)于LeetCode-200. 島嶼數(shù)量【深度優(yōu)先搜索 廣度優(yōu)先搜索 并查集 數(shù)組 矩陣】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！