200. Number of Islands

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

solution

flood fill

• dfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        visited = [[False] * n for _ in range(m)]
        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        res: int = 0

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

    def dfs(self, i, j, grid, dirs, visited):
        if grid[i][j] == '0' or visited[i][j]:
            return

        visited[i][j] = True

        for dir in dirs:
            new_i = i + dir[0]
            new_j = j + dir[1]
            if new_i < 0 or new_i >= len(grid) or new_j < 0 or new_j >= len(grid[0]):
                continue

            self.dfs(new_i, new_j, grid, dirs, visited)

时间复杂度：O(mn) 空间复杂度：O(mn)

class Solution:
    def __init__(self):
        self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        res = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    res += 1
                    self.dfs(grid, i, j)
        return res

    def dfs(self, grid, i, j):
        if grid[i][j] == '0':
            return

        grid[i][j] = '0'
        for d in self.dirs:
            new_i = i + d[0]
            new_j = j + d[1]
            if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]):
                self.dfs(grid, new_i, new_j)

• bfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        res = 0
        visited = [[False] * n for _ in range(m)]
        dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

        for i in range(m):
            for j in range(n):
                if visited[i][j] == False and grid[i][j] == '1':
                    res += 1
                    self.bfs(grid, i, j, visited, dirs, m, n)

        return res

    def bfs(self, grid, i, j, visited, dirs, m, n):
        q = collections.deque([(i, j)])
        visited[i][j] = True

        while q:
            i, j = q.popleft()

            for dir in dirs:
                new_i = i + dir[0]
                new_j = j + dir[1]
                if new_i >= 0 and new_i < m and new_j >= 0 and new_j < n and grid[new_i][new_j] == '1' and visited[new_i][new_j] == False:
                    q.append([new_i, new_j])
                    visited[new_i][new_j] = True

时间复杂度：O(mn) 空间复杂度：O()

• union find

follow up-岛屿类

• 大数据量: grid特别大，放不进内存，你怎么做？

  • union-find有巨大优势，可以一行一行的处理，这样每次读入内存两行数据就行

305 Number of Islands II

1905. Count Sub Islands

• 遍历图1为水、图2为岛的图2所有岛屿，标记为水；然后统计图2的岛屿

class Solution:
    def __init__(self):
        self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m = len(grid1)
        n = len(grid1[0])

        for i in range(m):
            for j in range(n):
                if grid1[i][j] == 0 and grid2[i][j] == 1:  # 注意这里的逻辑
                    self.dfs(i, j, grid2)

        res = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    res += 1
                    self.dfs(i, j, grid2)
        return res

    def dfs(self, i, j, grid2):
        grid2[i][j] = 0

        for dir in self.dirs:
            new_i = i + dir[0]
            new_j = j + dir[1]
            if 0 <= new_i < len(grid2) and 0 <= new_j < len(grid2[0]) and grid2[new_i][new_j] == 1:
                self.dfs(new_i, new_j, grid2)

时间复杂度：O() 空间复杂度：O()

827. Making A Large Island

class Solution:
    def __init__(self):
        self.dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)]

    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        islands = {}

        def bfs(row, column, island_id):
            queue = deque([(row, column, island_id)])
            area = 1
            visited.add((row, column))  # list is unhashable
            while queue:
                row, column, island_id = queue.pop()
                islands[(row, column)] = island_id
                for dir in self.dirs:
                    r = row + dir[0]
                    c = column + dir[1]
                    if 0 <= r < n and 0 <= c < n and grid[r][c] == 1 and (r, c) not in visited:
                        queue.append([r, c, island_id])
                        visited.add((r, c))
                        area += 1
            return area

        visited = set()
        area = {}
        island_id = 0
        for row in range(n):
            for column in range(n):
                if grid[row][column] == 1 and (row, column) not in visited:
                    area[island_id] = bfs(row, column, island_id)
                    island_id += 1

        if len(islands.keys()) == n**2: return n**2  # 特殊情况

        largest_area = 1
        for row in range(n):
            for column in range(n):
                if grid[row][column] == 1:
                    continue

                neighbors = set()  # 以要改变的0为基准，从四个方向中寻找邻居的island
                this_area = 1
                for dir in self.dirs:
                    r = row + dir[0]
                    c = column + dir[1]
                    if 0 <= r < n and 0 <= c < n and grid[r][c] == 1 and islands[(r, c)] not in neighbors:
                        neighbors.add(islands[(r, c)])
                        this_area += area[islands[(r, c)]]
                largest_area = max(largest_area, this_area)
        return largest_area

时间复杂度：O() 空间复杂度：O()

1020. Number of Enclaves

时间复杂度：O() 空间复杂度：O()

1254. Number of Closed Islands

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        def dfs(i: int, j: int) -> None:
            if i < 0 or i == m or j < 0 or j == n:
                return
            if grid[i][j] == 1:
                return

            grid[i][j] = 1
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)

        # Remove the lands connected to the edge.
        for i in range(m):
            for j in range(n):
                if i * j == 0 or i == m - 1 or j == n - 1:
                    if grid[i][j] == 0:
                        dfs(i, j)

        ans = 0

        # Reduce to 200. Number of Islands
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    dfs(i, j)
                    ans += 1

        return ans

时间复杂度：O() 空间复杂度：O()

• 有case不通过的错误做法, 还没去找原因

class Solution:
    def __init__(self):
        self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    def closedIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        if m < 3 or n < 3:
            return 0

        visited = [[False] * n for _ in range(m)]
        res = 0

        # 去掉最外圈后开始循环查找
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if visited[i][j]:
                    continue
                if grid[i][j] == 0:
                    if self.dfs(grid, i, j, visited):
                        res += 1
        return res

    def dfs(self, grid, i, j, visited):
        visited[i][j] = True

        for x, y in self.dirs:
            move_x = i + x
            move_y = j + y
            if move_x < 0 or move_x >= len(grid) or move_y < 0 or move_y >= len(grid[0]):
                return False
            if not visited[move_x][move_y] and grid[move_x][move_y] == 0:
                self.dfs(grid, move_x, move_y, visited)

        return True

463. Island Perimeter

# 记录岛屿cell数量与neighbour数量 -> 引申题目, 求最大周长的岛屿
# 注意: neighbor是一个双向关系，定义好哪个cell的时候求即可

时间复杂度：O() 空间复杂度：O()