图论之岛屿系列

图论之岛屿系列

形成模板进行学习，加快学习效率

深度优先遍历

# 可以直接改原始grid的采用直接改的方案来完成修改，减少了内存开支
def dfs(self, grid, i, j):
	if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == "0": # 过滤条件
           return
       grid[i][j] = "0" # 写变换条件
       self.dfs(grid, i - 1, j)
       self.dfs(grid, i + 1, j)
       self.dfs(grid, i, j - 1)
       self.dfs(grid, i, j + 1)
       return

# 无法改原始grid，需要visible辅助
def dfs(self, grid, visible, i, j):
    if (
        i < 0
        or j < 0
        or i >= len(grid)
        or j >= len(grid[0])
        or grid[i][j] == "0"
        or visible[i][j]
    ):
        return
    visible[i][j] = True
    self.dfs(grid, visible, i - 1, j)
    self.dfs(grid, visible, i + 1, j)
    self.dfs(grid, visible, i, j - 1)
    self.dfs(grid, visible, i, j + 1)
    return

广度优先遍历

# 原有grid进行处理
def bfs(self, grid, i, j):
    queue = deque([[i, j]])
    grid[i][j] = "0"

    while queue:
        cur_x, cur_y = queue.pop()
        if cur_x - 1 >= 0 and grid[cur_x - 1][cur_y] == "1":
            queue.append([cur_x - 1, cur_y])
            grid[cur_x - 1][cur_y] = "0"
        if cur_x + 1 < len(grid) and grid[cur_x + 1][cur_y] == "1":
            queue.append([cur_x + 1, cur_y])
            grid[cur_x + 1][cur_y] = "0"
        if cur_y - 1 >= 0 and grid[cur_x][cur_y - 1] == "1":
            queue.append([cur_x, cur_y - 1])
            grid[cur_x][cur_y - 1] = "0"
        if cur_y + 1 < len(grid[0]) and grid[cur_x][cur_y + 1] == "1":
            queue.append([cur_x, cur_y + 1])
            grid[cur_x][cur_y + 1] = "0"
    return

# 提供辅助visible进行处理
def bfs(self, grid, nums, i, j):
	queue = deque([[i, j]])
	nums.add((i, j))
	
	while queue:
	    cur_x, cur_y = queue.pop()
	    if (
	        cur_x - 1 >= 0
	        and grid[cur_x - 1][cur_y] >= grid[cur_x][cur_y]
	        and (cur_x - 1, cur_y) not in nums
	    ):
	        queue.append([cur_x - 1, cur_y])
	        nums.add((cur_x - 1, cur_y))
	    if (
	        cur_x + 1 < len(grid)
	        and grid[cur_x + 1][cur_y] >= grid[cur_x][cur_y]
	        and (cur_x + 1, cur_y) not in nums
	    ):
	        queue.append([cur_x + 1, cur_y])
	        nums.add((cur_x + 1, cur_y))
	    if (
	        cur_y - 1 >= 0
	        and grid[cur_x][cur_y - 1] >= grid[cur_x][cur_y]
	        and (cur_x, cur_y - 1) not in nums
	    ):
	        queue.append([cur_x, cur_y - 1])
	        nums.add((cur_x, cur_y - 1))
	    if (
	        cur_y + 1 < len(grid[0])
	        and grid[cur_x][cur_y + 1] >= grid[cur_x][cur_y]
	        and (cur_x, cur_y + 1) not in nums
	    ):
	        queue.append([cur_x, cur_y + 1])
	        nums.add((cur_x, cur_y + 1))
	return

实例

岛屿数量题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例：

3

在这里插入图片描述
实现方案
将遍历过的grid设置为0

  1. 深度优先遍历
class Solution:
    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == "0":
            return
        grid[i][j] = "0"
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i, j - 1)
        self.dfs(grid, i, j + 1)
        return

    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        cnt = 0

        for i, j in product(range(m), range(n)):
            if grid[i][j] == "1":
                self.dfs(grid, i, j)
                cnt += 1
        return cnt
  1. 广度优先遍历
class Solution:
    def bfs(self, grid, i, j):
        queue = deque([[i, j]])
        grid[i][j] = "0"

        while queue:
            cur_x, cur_y = queue.pop()
            if cur_x - 1 >= 0 and grid[cur_x - 1][cur_y] == "1":
                queue.append([cur_x - 1, cur_y])
                grid[cur_x - 1][cur_y] = "0"
            if cur_x + 1 < len(grid) and grid[cur_x + 1][cur_y] == "1":
                queue.append([cur_x + 1, cur_y])
                grid[cur_x + 1][cur_y] = "0"
            if cur_y - 1 >= 0 and grid[cur_x][cur_y - 1] == "1":
                queue.append([cur_x, cur_y - 1])
                grid[cur_x][cur_y - 1] = "0"
            if cur_y + 1 < len(grid[0]) and grid[cur_x][cur_y + 1] == "1":
                queue.append([cur_x, cur_y + 1])
                grid[cur_x][cur_y + 1] = "0"
        return

    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        cnt = 0

        for i, j in product(range(m), range(n)):
            if grid[i][j] == "1":
                self.bfs(grid, i, j)
                cnt += 1
        return cnt

岛屿的最大面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

4

提示信息
在这里插入图片描述
样例输入中，岛屿的最大面积为 4。

数据范围：

方案：
与岛屿数量一致，增加一个计数功能即可

  1. 深度优先遍历
class Solution:
    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
            return
        self.cnt += 1
        grid[i][j] = 0
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i, j - 1)
        self.dfs(grid, i, j + 1)
        return

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        maxN = 0
        m, n = len(grid), len(grid[0])


        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                self.cnt = 0
                self.dfs(grid, i, j)
                maxN = max(maxN, self.cnt)
        return maxN
  1. 广度优先遍历
class Solution:
    def bfs(self, grid, i, j):
        queue = deque([[i, j]])
        grid[i][j] = 0
        cnt = 1

        while queue:
            cur_x, cur_y = queue.pop()
            if cur_x - 1 >= 0 and grid[cur_x - 1][cur_y] == 1:
                queue.append([cur_x - 1, cur_y])
                grid[cur_x - 1][cur_y] = 0
                cnt += 1
            if cur_x + 1 < len(grid) and grid[cur_x + 1][cur_y] == 1:
                queue.append([cur_x + 1, cur_y])
                grid[cur_x + 1][cur_y] = 0
                cnt += 1
            if cur_y - 1 >= 0 and grid[cur_x][cur_y - 1] == 1:
                queue.append([cur_x, cur_y - 1])
                grid[cur_x][cur_y - 1] = 0
                cnt += 1
            if cur_y + 1 < len(grid[0]) and grid[cur_x][cur_y + 1] == 1:
                queue.append([cur_x, cur_y + 1])
                grid[cur_x][cur_y + 1] = 0
                cnt += 1
        return cnt

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        maxN = 0
        m, n = len(grid), len(grid[0])

        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                cnt = self.bfs(grid, i, j)
                maxN = max(maxN, cnt)
        return maxN

孤岛的总面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例：

1

提示信息：
在这里插入图片描述
解题思路：
反方向法，求孤岛，只需要把不是孤岛的给变成海即可，剩下的都是孤岛，不是孤岛的需要从上下左右边界进行海化

  1. 深度优先遍历
class Solution:

    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
            return
        grid[i][j] = 0
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i, j - 1)
        self.dfs(grid, i, j + 1)

    def SumAreaIsolatedLand(self, grid):
        m, n = len(grid), len(grid[0])
        sumN = 0

        for j in [0, -1]:
            for i in range(m):
                if grid[i][j] == 1:
                    self.dfs(grid, i, j)

        for i in [0, -1]:
            for j in range(1, n - 1):
                if grid[i][j] == 1:
                    self.dfs(grid, i, j)

        for i, j in product(range(1, m - 1), range(1, n - 1)):
            if grid[i][j] == 1:
                sumN += 1
        return sumN
  1. 广度优先遍历
class Solution:

    def bfs(self, grid, i, j):
        queue = deque([[i, j]])
        grid[i][j] = 0

        while queue:
            cur_x, cur_y = queue.pop()
            if cur_x - 1 >= 0 and grid[cur_x - 1][cur_y] == 1:
                queue.append([cur_x - 1, cur_y])
                grid[cur_x - 1][cur_y] = 0
            if cur_x + 1 < len(grid) and grid[cur_x + 1][cur_y] == 1:
                queue.append([cur_x + 1, cur_y])
                grid[cur_x + 1][cur_y] = 0
            if cur_y - 1 >= 0 and grid[cur_x][cur_y - 1] == 1:
                queue.append([cur_x, cur_y - 1])
                grid[cur_x][cur_y - 1] = 0
            if cur_y + 1 < len(grid[0]) and grid[cur_x][cur_y + 1] == 1:
                queue.append([cur_x, cur_y + 1])
                grid[cur_x][cur_y + 1] = 0
        return

    def SumAreaIsolatedLand(self, grid):
        m, n = len(grid), len(grid[0])
        sumN = 0

        for j in [0, -1]:
            for i in range(m):
                if grid[i][j] == 1:
                    self.bfs(grid, i, j)

        for i in [0, -1]:
            for j in range(1, n - 1):
                if grid[i][j] == 1:
                    self.bfs(grid, i, j)

        for i, j in product(range(1, m - 1), range(1, n - 1)):
            if grid[i][j] == 1:
                sumN += 1
        return sumN

沉没孤岛

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出将孤岛“沉没”之后的岛屿矩阵。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1

提示信息
在这里插入图片描述
方案：
与孤岛总面不同的是，需要在原有grid上进行操作，不可以直接对grid进行调整，增加visible来控制非孤岛的位置，最后遍历，仍然为1的便是孤岛

  1. 深度优先遍历
class Solution:
    def dfs(self, grid, visible, i, j):
        if (
            i < 0
            or j < 0
            or i >= len(grid)
            or j >= len(grid[0])
            or grid[i][j] == 0
            or visible[i][j] is True
        ):
            return
        visible[i][j] = True
        self.dfs(grid, visible, i - 1, j)
        self.dfs(grid, visible, i + 1, j)
        self.dfs(grid, visible, i, j - 1)
        self.dfs(grid, visible, i, j + 1)
        return

    def DownIsolatedLand(self, grid):
        m, n = len(grid), len(grid[0])

        visible = [[False] * n for _ in range(m)]

        for i in [0, -1]:
            for j in range(1, n - 1):
                if grid[i][j] == 1:
                    self.dfs(grid, visible, i, j)

        for j in [0, -1]:
            for i in range(1, m - 1):
                if grid[i][j] == 1:
                    self.dfs(grid, visible, i, j)

        for i, j in product(range(1, m - 1), range(1, n - 1)):
            if grid[i][j] == 1 and visible[i][j] is False:
                grid[i][j] = 0
        return
  1. 广度优先遍历
class Solution:
    def bfs(self, grid, visible, i, j):
        queue = deque([[i, j]])
        visible[i][j] = True

        while queue:
            cur_x, cur_y = queue.pop()
            if (
                cur_x - 1 >= 0
                and grid[cur_x - 1][cur_y] == 1
                and visible[cur_x - 1][cur_y] is False
            ):
                queue.append([cur_x - 1, cur_y])
                visible[cur_x - 1][cur_y] = True
            if (
                cur_x + 1 < len(grid)
                and grid[cur_x + 1][cur_y] == 1
                and visible[cur_x + 1][cur_y] is False
            ):
                queue.append([cur_x + 1, cur_y])
                visible[cur_x + 1][cur_y] = True
            if (
                cur_y - 1 >= 0
                and grid[cur_x][cur_y - 1] == 1
                and visible[cur_x][cur_y - 1] is False
            ):
                queue.append([cur_x, cur_y - 1])
                visible[cur_x][cur_y - 1] = True
            if (
                cur_y + 1 < len(grid[0])
                and grid[cur_x][cur_y + 1] == 1
                and visible[cur_x][cur_y + 1] is False
            ):
                queue.append([cur_x, cur_y + 1])
                visible[cur_x][cur_y + 1] = True
        return

    def DownIsolatedLand(self, grid):
        m, n = len(grid), len(grid[0])

        visible = [[False] * n for _ in range(m)]

        for i in [0, -1]:
            for j in range(1, n - 1):
                if grid[i][j] == 1:
                    self.bfs(grid, visible, i, j)

        for j in [0, -1]:
            for i in range(1, m - 1):
                if grid[i][j] == 1:
                    self.bfs(grid, visible, i, j)

        for i, j in product(range(1, m - 1), range(1, n - 1)):
            if grid[i][j] == 1 and visible[i][j] is False:
                grid[i][j] = 0
        return

水流问题

题目描述：

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入描述：

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

输出描述：

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

输入示例：

5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1

输出示例：

0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1

提示信息：

在这里插入图片描述
图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

解题思路：
从上左边界和右下边界作为始点，水流开始往高处流动，最终取两个方向的交集，说明即可往第一组边界流动，也可以往第二组边界流动

  1. 深度优先遍历
class Solution:
    def dfs(self, grid, nums, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or (i, j) in nums:
            return
        nums.add((i, j))
        if i - 1 >= 0 and grid[i][j] <= grid[i - 1][j]:
            self.dfs(grid, nums, i - 1, j)
        if i + 1 < len(grid) and grid[i][j] <= grid[i + 1][j]:
            self.dfs(grid, nums, i + 1, j)
        if j - 1 >= 0 and grid[i][j] <= grid[i][j - 1]:
            self.dfs(grid, nums, i, j - 1)
        if j + 1 < len(grid[0]) and grid[i][j] <= grid[i][j + 1]:
            self.dfs(grid, nums, i, j + 1)
        return

    def WaterFlow(self, grid):
        m, n = len(grid), len(grid[0])

        num1 = set()
        num2 = set()
        for i in range(m):
            self.dfs(grid, num1, i, 0)
            self.dfs(grid, num2, i, n - 1)

        for j in range(n):
            self.dfs(grid, num1, 0, j)
            self.dfs(grid, num2, m - 1, j)
        return list(num1 & num2)
  1. 广度优先遍历
class Solution:
    def bfs(self, grid, nums, i, j):
        queue = deque([[i, j]])
        nums.add((i, j))

        while queue:
            cur_x, cur_y = queue.pop()
            if (
                cur_x - 1 >= 0
                and grid[cur_x - 1][cur_y] >= grid[cur_x][cur_y]
                and (cur_x - 1, cur_y) not in nums
            ):
                queue.append([cur_x - 1, cur_y])
                nums.add((cur_x - 1, cur_y))
            if (
                cur_x + 1 < len(grid)
                and grid[cur_x + 1][cur_y] >= grid[cur_x][cur_y]
                and (cur_x + 1, cur_y) not in nums
            ):
                queue.append([cur_x + 1, cur_y])
                nums.add((cur_x + 1, cur_y))
            if (
                cur_y - 1 >= 0
                and grid[cur_x][cur_y - 1] >= grid[cur_x][cur_y]
                and (cur_x, cur_y - 1) not in nums
            ):
                queue.append([cur_x, cur_y - 1])
                nums.add((cur_x, cur_y - 1))
            if (
                cur_y + 1 < len(grid[0])
                and grid[cur_x][cur_y + 1] >= grid[cur_x][cur_y]
                and (cur_x, cur_y + 1) not in nums
            ):
                queue.append([cur_x, cur_y + 1])
                nums.add((cur_x, cur_y + 1))
        return

    def WaterFlow(self, grid):
        m, n = len(grid), len(grid[0])

        num1 = set()
        num2 = set()
        for i in range(m):
            self.bfs(grid, num1, i, 0)
            self.bfs(grid, num2, i, n - 1)

        for j in range(n):
            self.bfs(grid, num1, 0, j)
            self.bfs(grid, num2, m - 1, j)
        return list(num1 & num2)

建造最大岛屿

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述：

输出一个整数，表示最大的岛屿面积。如果矩阵中不存在岛屿，则输出 0。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

6

提示信息
在这里插入图片描述
对于上面的案例，有两个位置可将 0 变成 1，使得岛屿的面积最大，即 6。

在这里插入图片描述
解决方案：

  1. 分区遍历，将一块岛屿按照新的序号保留下来，同时计算出对应的面积
  2. 遍历grid==0的区域，进行连通，确定最大值
  1. 深度优先遍历：
class Solution:
    def dfs(self, grid, index, i, j):
        if (
            i < 0
            or j < 0
            or i >= len(grid)
            or j >= len(grid[0])
            or grid[i][j] in [0, index]
        ):
            return
        self.cnt += 1
        grid[i][j] = index
        self.dfs(grid, index, i - 1, j)
        self.dfs(grid, index, i + 1, j)
        self.dfs(grid, index, i, j - 1)
        self.dfs(grid, index, i, j + 1)
        return

    def BuildLand(self, grid):
        record = {0: 0}
        m, n = len(grid), len(grid[0])
        index = 2
        maxN = 0
        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                self.cnt = 0
                self.dfs(grid, index, i, j)
                record[index] = self.cnt
                index += 1
                maxN = max(maxN, self.cnt)

        for i, j in product(range(m), range(n)):
            if grid[i][j] == 0:
                sumN = 1
                if i - 1 >= 0:
                    sumN += record[grid[i - 1][j]]
                if i + 1 < m:
                    sumN += record[grid[i + 1][j]]
                if j - 1 >= 0:
                    sumN += record[grid[i][j - 1]]
                if j + 1 < n:
                    sumN += record[grid[i][j + 1]]

                maxN = max(maxN, sumN)
        return maxN
  1. 广度优先遍历
class Solution:
    def bfs(self, grid, index, i, j):
        queue = deque([[i, j]])
        grid[i][j] = index
        cnt = 1
        while queue:
            cur_x, cur_y = queue.pop()

            if cur_x - 1 >= 0 and grid[cur_x - 1][cur_y] == 1:
                queue.append([cur_x - 1, cur_y])
                grid[cur_x - 1][cur_y] = index
                cnt += 1
            if cur_x + 1 < len(grid) and grid[cur_x + 1][cur_y] == 1:
                queue.append([cur_x + 1, cur_y])
                grid[cur_x + 1][cur_y] = index
                cnt += 1
            if cur_y - 1 >= 0 and grid[cur_x][cur_y - 1] == 1:
                queue.append([cur_x, cur_y - 1])
                grid[cur_x][cur_y - 1] = index
                cnt += 1
            if cur_y + 1 < len(grid[0]) and grid[cur_x][cur_y + 1] == 1:
                queue.append([cur_x, cur_y + 1])
                grid[cur_x][cur_y + 1] = index
                cnt += 1
        return cnt

    def BuildLand(self, grid):
        record = {0: 0}
        m, n = len(grid), len(grid[0])
        index = 2
        maxN = 0
        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                cnt = self.bfs(grid, index, i, j)
                record[index] = cnt
                index += 1
                maxN = max(maxN, cnt)

        for i, j in product(range(m), range(n)):
            if grid[i][j] == 0:
                sumN = 1
                if i - 1 >= 0:
                    sumN += record[grid[i - 1][j]]
                if i + 1 < m:
                    sumN += record[grid[i + 1][j]]
                if j - 1 >= 0:
                    sumN += record[grid[i][j - 1]]
                if j + 1 < n:
                    sumN += record[grid[i][j + 1]]

                maxN = max(maxN, sumN)
        return maxN

岛屿的周长

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。

你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的周长。

输入示例

5 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

输出示例

14

提示信息

在这里插入图片描述
岛屿的周长为 14。

解决方案：
从左上往右下遍历，如果当前位置为1，那周长会增加4，如果当前位置左/下位置也为1，那将会减少2条边，所以只需要计数即可

from itertools import product


class Solution:
    def LaneLength(self, grid):
        m, n = len(grid), len(grid[0])
        cnt1 = 0
        cnt2 = 0
        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                cnt1 += 1
                if i + 1 < m and grid[i + 1][j] == 1:
                    cnt2 += 1
                if j + 1 < n and grid[i][j + 1] == 1:
                    cnt2 += 1
        return 4 * cnt1 - 2 * cnt2

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/719454.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【大数据·hadoop】项目实践：IDEA实现WordCount词频统计项目

【大数据·hadoop】项目实践：IDEA实现WordCount词频统计项目

一、环境准备 1.1&#xff1a;在ubuntu上安装idea 我们知道&#xff0c;在hdfs分布式系统中&#xff0c;MapReduce这部分程序是需要用户自己开发&#xff0c;我们在ubuntu上安装idea也是为了开发wordcount所需的Map和Reduce程序&#xff0c;最后打包&#xff0c;上传到hdfs上…
阅读更多...
金蝶云星空程序员开发快速入门

金蝶云星空程序员开发快速入门

文章目录 一 前言1.1 学习步骤1.2 学习需知 二、学习金蝶*云星空的步骤2.1 下载金蝶*云星空安装到本地2.2 查看官网的学习资料2.3 如何使用C#进行插件开发2.4 sqlserver的表设计以及存储过程2.5 如何使用python进行插件的开发2.6 第三方程序如何调用金蝶*云星空的数据 三 后记 …
阅读更多...
LangGraph自适应RAG

LangGraph自适应RAG

LangGraph自适应RAG 介绍索引LLMsweb 搜索工具graphgraph stategraph flowbuild graph执行 介绍 自适应 RAG 是一种 RAG 策略&#xff0c;它将 (1) 查询分析 (2) 主动/自校正 RAG 结合起来。 在文章中&#xff0c;他们报告了查询分析到路由获取&#xff1a; No RetrievalSing…
阅读更多...
示例:WPF中应用Grid的SharedSizeGroup设置整齐的布局

示例:WPF中应用Grid的SharedSizeGroup设置整齐的布局

一、目的&#xff1a;应用Grid的SharedSizeGroup设置整齐的布局 二、实现 <ItemsControl ItemsSource"{local:GetStudents Count5}"><ItemsControl.ItemTemplate><DataTemplate><Grid ShowGridLines"True"><Grid.ColumnDefinit…
阅读更多...
无代码爬虫八爪鱼采集器-如何采集携程网指定酒店差评信息

无代码爬虫八爪鱼采集器-如何采集携程网指定酒店差评信息

场景描述&#xff1a;有一些酒店会分析同行的差评原因&#xff0c;以便提前做预案&#xff0c;避免自己酒店也放同样的错误。他们通过采集携程网指定酒店的提取中差评&#xff0c;使用的采集工具为无代码爬虫软件八爪鱼采集器免费版&#xff0c;下载链接&#xff1a;1.软件分享…
阅读更多...
龙芯的 新世界 与 旧世界

龙芯的 新世界 与 旧世界

但是基本可以 确定 旧世界应该是 有 mips 的代码的。 新世界 应该是 loongarch . 这是 龙芯派 2k300 的连接。 6.Github相关仓库 龙芯派相关源码仓库&#xff1a;https://github.com/LoongsonDotNETCommunity/LoongsonPI 龙芯派Cookbook仓库&#xff1a;https://github.com/L…
阅读更多...
LangChain入门学习笔记（一）——Hello World

LangChain入门学习笔记（一）——Hello World

什么是LangChain LangChain是一个开源&#xff08;github repo&#xff09;的大语言模型应用开发框架&#xff0c;提供了一整套的工具、方法和接口去帮助程序员构建基于大语言模型的端到端应用。LangChain是长链&#xff08;long chain&#xff09;的意思&#xff0c;它的一个…
阅读更多...
二叉树专题

二叉树专题

94. 二叉树的中序遍历 给定一个二叉树的根节点 root &#xff0c;返回 它的 中序 遍历 。递归实现【左->根->右】 import java.util.*; /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* …
阅读更多...
中国最厉害的改名大师颜廷利：食物的真正人生意义是识悟

中国最厉害的改名大师颜廷利：食物的真正人生意义是识悟

在探索人生意义的深邃征途中&#xff0c;我们本应以“识悟”为航标&#xff0c;不断扬帆远航&#xff0c;以实现自我的升华。然而&#xff0c;当回望人世繁华&#xff0c;古往今来&#xff0c;无论男女老少&#xff0c;似乎都在“食物”的陪伴下&#xff0c;徘徊往复&#xff0…
阅读更多...
nc网络收发测试-tcp客户端\TCP服务器\UDP\UDP广播

nc网络收发测试-tcp客户端\TCP服务器\UDP\UDP广播

netcat&#xff08;nc&#xff09;&#xff1a; 作用&#xff1a;一个功能强大的网络工具&#xff0c;提供了简单的网络测试和网络编程功能。工作原理&#xff1a;可以用于建立TCP或UDP连接&#xff0c;并发送和接收数据。示例用法&#xff1a; 监听TCP端口&#xff1a;nc -l 1…
阅读更多...
在低侧电流检测中使用单端放大器：误差源和布局技巧

在低侧电流检测中使用单端放大器：误差源和布局技巧

低侧检测的主要优点是可以使用相对简单的配置来放大分流电阻器两端的电压。例如&#xff0c;通用运算放大器的同相配置可能是需要能够在消费市场领域竞争的成本敏感型电机控制应用的有效选择。 基于同相配置的电路图如图1所示。 图1。 然而&#xff0c;这种低成本解决方案可能…
阅读更多...
java实现图片水印添加并自动上传七牛云

java实现图片水印添加并自动上传七牛云

图片左下角水印添加 满足需求&#xff1a;可以对不同类型尺寸的照片、图片进行水印的添加&#xff0c;实现尺寸自适应添加水印。 水印效果 代码实现 Controller package com.wlh.zetc.restore.controller;import cn.hutool.core.date.DateUtil; import com.alibaba.nacos.c…
阅读更多...
前端可观测性系统建设

前端可观测性系统建设

一. 背景 随着前端业务的日趋庞大&#xff0c;及时发现和解决业务中的问题、优化用户体验、实时监控业务健康度变得愈发重要。在业务层面&#xff0c;我们希望能够监控每次发布版本后&#xff0c;核心功能是否有显著提升或至少没有负面影响&#xff0c;核心接口是否正常运作&a…
阅读更多...
太速科技-基于XCVU9P+ C6678的100G光纤的加速卡

太速科技-基于XCVU9P+ C6678的100G光纤的加速卡

基于XCVU9P C6678的100G光纤的加速卡 一、板卡概述 二、技术指标 • 板卡为自定义结构&#xff0c;板卡大小332mmx260mm; • FPGA采用Xilinx Virtex UltralSCALE 系列芯片 XCVU9P; • FPGA挂载4组FMC HPC 连接器; • 板载4路QSPF&#xff0c;每路数据速…
阅读更多...
【深度学习驱动流体力学】剖析流体力学可视化paraview原理

【深度学习驱动流体力学】剖析流体力学可视化paraview原理

目录 1.paraview版本2.配置过程检查插件库文件配置 ParaView 环境变量启动 ParaView 并检查插件3.可视化测试插件功能 3.加载数据进行可视化第一步: 导入案例第二步:查看当前目录未更新前的内容第三步:使用 blockMesh 命令生成腔体案例的网格第四步:运行仿真icoFoam第五步:使用…
阅读更多...
ESP32蓝牙串口通讯

ESP32蓝牙串口通讯

文章目录 一、前言二、代码三、运行 一、前言 ESP32支持经典蓝牙和低功耗蓝牙&#xff08;BLE&#xff09;,经典蓝牙可在计算机上模拟出一个串口&#xff0c;使得ESP32可以以串口的方式和计算机通信。 二、代码 #include "BluetoothSerial.h"String device_name …
阅读更多...
以CMDB为基础构建DevOps平台体系

以CMDB为基础构建DevOps平台体系

在当今数字化转型的浪潮中&#xff0c;企业IT运维模式正从传统的资产管理向现代化的资源管理转变。配置管理数据库&#xff08;CMDB&#xff09;作为IT运维的核心组成部分&#xff0c;其在DevOps平台中的重要性愈加凸显。通过国信证券和招商银行的实际案例&#xff0c;我们将详…
阅读更多...
Redis缓存与数据库双写不一致及解决方法

Redis缓存与数据库双写不一致及解决方法

1.缓存与数据库双写不一致 在大并发下&#xff0c;同时操作数据库与缓存会存在数据不一致性问题 1.1 双写不一致情况 1.2 读写并发不一致 2.解决方法 对于并发几率很小的数据(如个人维度的订单数据、用户数据等)&#xff0c;这种几乎不用考虑这个问题&#xff0c;很少会发生…
阅读更多...
Stable Diffusion 3 开源了，完全不输 Midjourney

Stable Diffusion 3 开源了，完全不输 Midjourney

前段时间我介绍过一款文字生视频的 AI 工具&#xff1a; SadTalker&#xff0c; 当时咱们是作为 Stable Diffusion 的插件来安装的。 那基于 Stable Diffusion 呢&#xff0c;咱们今天就来聊聊新开源的 Stable Diffusion 3。 在文字生成图片这个领域&#xff0c;一直是有三个…
阅读更多...
springSecurity(二)：实现登入获取token与解析token

springSecurity(二)：实现登入获取token与解析token

登入生成token 主要思想 springSecurity使用UsernamePasswordAuthenticationToken类来封装用户名和密码的认证信息 代码实现 发起登入请求后&#xff0c;进入到login()方法 /*** 在接口中我们通过AuthenticationManager的authenticate方法来进行用户认证,* 所以需要在Secur…
阅读更多...
最新文章

Copyright @ 2022~2023