1、本次总结的题目通常是在二维矩阵考察连通域/岛屿问题，常用的方法包括深度优先搜索、广度优先搜索和并查集，根据具体的题目可以选择最合适的方法，我个人优选在逻辑思维上简单直观的广度优先搜索方法
2、二维矩阵考察连通域/岛屿问题，包括简单的连通域染色、岛屿数量、飞地数量、岛屿面积等，复杂一点的题目考察对每个连通域/岛屿如何更好地标记，比如最大人工岛（简单的数字标记）、岛屿形状（相对位置连起来的元组或字符串标记）等

733. 图像渲染

本题是连通域染色问题的基础题目，是深度优先搜索或广度优先搜索的基本练习题，需要注意不用染色的特殊情况，比较细节

from typing import List
from collections import deque
'''
733. 图像渲染
有一幅以m x n的二维整数数组表示的图画image，其中image[i][j]表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素image[sr][sc]开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，
接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。
将所有有记录的像素点的颜色值改为newColor。
最后返回 经过上色渲染后的图像。
示例 1:输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2输出: [[2,2,2],[2,2,0],[2,0,1]]解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
题眼：连通域染色问题，DFS、BFS的基础操作
'''class Solution:def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:# 思路1、深度优先搜索# 情况1、矩阵为空if not image:return imagem, n = len(image), len(image[0])val = image[sr][sc]# 情况2、矩阵不用染色if val == color:return image# 情况3、深度优先搜索# 1、定义递归函数def dfs(x, y):# 2、终止条件if not 0 <= x < m or not 0 <= y < n or image[x][y] != val:  # 不合法&非连通 直接返回return# 3、递归操作image[x][y] = colordfs(x+1, y)dfs(x-1, y)dfs(x, y+1)dfs(x, y-1)dfs(sr, sc)return image# # 思路2、广度优先搜索# # 情况1、矩阵为空# if not image:#     return image# m, n = len(image), len(image[0])# val = image[sr][sc]# # 情况2、矩阵不用染色# if val == color:#     return image# 情况3、广度优先搜索# que = deque()# que.append((sr, sc))# image[sr][sc] = color  # 入队立刻染色# while que:#     x, y = que.popleft()#     for tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):  # 沿 4个方向 搜索#         if 0 <= tx < m and 0 <= ty < n and image[tx][ty] == val:  # 合法&连通 才入队#             que.append((tx, ty))#             image[tx][ty] = color  # 入队立刻染色# return imageif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')in_line1 = in_line[1].strip().split('s')[0].strip()[1: -2]image = []for row in in_line1.split(']')[: -1]:image.append([int(i) for i in row.split('[')[1].split(',')])sr = int(in_line[2].strip().split(',')[0])sc = int(in_line[3].strip().split(',')[0])newColor = int(in_line[4].strip())print(obj.floodFill(image, sr, sc, newColor))except EOFError:break

1034. 边界着色

”733. 图像渲染“的扩展，理解题很重要：只对连通域的边界位置的方块着色，可以把边界方块放到一个列表中，遍历完矩阵后再染色

from typing import List
from collections import deque
'''
1034. 边界着色
给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
两个网格块属于同一 连通分量 需满足下述全部条件：两个网格块颜色相同在上、下、左、右任意一个方向上相邻
连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻在网格的边界上（第一行/列或最后一行/列）
请你使用指定颜色color 为所有包含网格块grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格grid 。
示例 1:输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3输出：[[3,3],[3,2]]
题眼：”733. 图像渲染“的扩展，理解题很重要：只对连通域的边界方块着色，可以把边界方块放到一个列表中
思路：第一步，找到 “连通区域”的边界方块，并把它保存起来第二步，对保存的边界方块进行着色
细节：如果color==grid[row][col]，则不必着色，更不必寻找 “连通区域”的边界
'''class Solution:def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:# 理解题很重要：只对边界区域着色，可以把边界位置放到一个列表中# 思路1、广度优先遍历# # 情况1、矩阵为空# if not grid:#     return []# # 情况2、不需要着色# if grid[row][col] == color:#     return grid# # 情况3、需要着色# que = deque()# m, n = len(grid), len(grid[0])# visited = [[False] * n for _ in range(m)]# que.append((row, col))# visited[row][col] = True  # 入队就标记# target = grid[row][col]# border = []# while len(que) > 0:#     x, y = que.popleft()#     # 对连通域的每个块判断是否为边界#     if x == 0 or x == m-1 or y == 0 or y == n-1:#         border.append((x, y))#     elif grid[x+1][y] != target or grid[x-1][y] != target or grid[x][y+1] != target or grid[x][y-1] != target:#         border.append((x, y))#     for tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):#         if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == target:#             que.append((tx, ty))#             visited[tx][ty] = True# for i, j in border:#     grid[i][j] = color# return grid# 思路2、深度优先遍历# 情况1、矩阵为空if not grid:return []# 情况2、不需要着色if grid[row][col] == color:return grid# 情况3、需要着色m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]target = grid[row][col]border = []# 1、定义递归函数def dfs(x: int, y: int):# 2、终止条件if not 0 <= x < m or not 0 <= y < n or visited[x][y] or grid[x][y] != target:return# 3、递归操作visited[x][y] = Trueif x == 0 or x == m-1 or y == 0 or y == n-1:border.append((x, y))elif grid[x+1][y] != target or grid[x-1][y] != target or grid[x][y+1] != target or grid[x][y-1] != target:border.append(((x, y)))dfs(x+1, y)dfs(x-1, y)dfs(x, y+1)dfs(x, y-1)dfs(row, col)for i, j in border:grid[i][j] = colorreturn gridif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')grid = []if in_line[1].strip().split('r')[0].strip()[1: -2] != '':for row in in_line[1].strip().split('r')[0].strip()[1: -2].split(']')[:-1]:grid.append([int(n) for n in row.split('[')[1].split(',')])row = int(in_line[2].split(',')[0])col = int(in_line[3].split(',')[0])color = int(in_line[4])print(obj.colorBorder(grid, row, col, color))except EOFError:break

200. 岛屿数量

1、岛屿数量问题的基础题目，也是考察连通域的个数，不像前面两道题一样给定起始的搜索位置了，需要对二维矩阵从首位置遍历到末位置进行搜索了，推荐简单直观的广度优先搜索方法
2、注意细节就是入队的位置及时标记，否则可能会超时

from typing import List, Optional, Union
from collections import deque
'''
200. 岛屿数量
给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]输出：1
模板：广搜或深搜都可以解决；只要能把相邻且相同属性的节点标记上就行。
题眼：连通域个数问题，DFS、BFS的基础操作
思路：采用visited矩阵标记访问过的位置，可以避免原矩阵被修改！
'''class Solution:def numIslands(self, grid: List[List[str]]) -> int:# 思路1、广度优先搜索# 特殊情况：区域为空if not grid:return 0result = 0m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]  # 标记矩阵que = deque()for i in range(m):for j in range(n):if grid[i][j] == '1' and not visited[i][j]:que.append((i, j))visited[i][j] = True  # 注意：必须立刻标记，否则会在后续有太多重复判断，会超时while len(que) > 0:x, y = que.popleft()for tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == '1':que.append((tx, ty))visited[tx][ty] = Trueresult += 1return result# # 思路2、深度优先搜索# # 特殊情况：区域为空# if not grid:#     return 0# result = 0# m, n = len(grid), len(grid[0])# visited = [[False] * n for _ in range(m)]  # 标记矩阵# # 1、定义递归函数# def dfs(x: int, y: int):#     # 2、终止条件#     if not 0 <= x < m or not 0 <= y < n or visited[x][y] or grid[x][y] != '1':#         return#     # 3、递归操作#     visited[x][y] = True#     dfs(x+1, y)#     dfs(x-1, y)#     dfs(x, y+1)#     dfs(x, y-1)# for i in range(m):#     for j in range(n):#         if grid[i][j] == '1' and not visited[i][j]:  # 注意：不可以在调用前进行标记处理，这样就无法实现dfs()递归#             dfs(i, j)#             result += 1# return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]grid = []for row in in_line.split(']')[: -1]:ans = []for s in row.split('[')[1].split(','):ans.append(s[1: -1])grid.append(ans)obj.numIslands(grid)print(grid)except EOFError:break

1020. 飞地的数量

”200. 岛屿数量“的扩展，正常广度优先搜索方法基础上，额外添加 连通域内方块个数统计及连通域是否为飞地的判断即可——只需要一次遍历即可

from typing import List, Optional, Union
from collections import deque
'''
1020. 飞地的数量
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量
示例 1:输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]输出：3解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
题眼：”200. 岛屿数量“的扩展，正常BFS遍历添加上 连通域内方块个数及连通域是否为飞地的判断即可——只需要一次遍历即可
按照这个思路改成DFS时，改不出来，我太菜了！
'''class Solution:def numEnclaves(self, grid: List[List[int]]) -> int:# 思路1、广度优先搜索# 情况1、矩阵为空if not grid:return 0# 情况2、矩阵不为空que = deque()m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]result = 0for i in range(m):for j in range(n):if grid[i][j] == 1 and not visited[i][j]:que.append((i, j))visited[i][j] = Truetemp_num = 1  # 记录连通域内单元格数量isEnclave = True  # 标记连通域是否为飞地while len(que) > 0:x, y = que.popleft()if isEnclave:if x == 0 or x == m-1 or y == 0 or y == n-1:isEnclave = Falsefor tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == 1:que.append((tx, ty))visited[tx][ty] = Truetemp_num += 1if isEnclave:result += temp_numreturn resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]grid = []for row in in_line.split(']')[: -1]:grid.append([int(i) for i in row.split('[')[1].split(',')])print(obj.numEnclaves(grid))except EOFError:break

1254. 统计封闭岛屿的数目

“1020. 飞地的数量”一样的题意，正常广度优先搜索方法基础上，额外添加 连通域是否为飞地的判断即可

from typing import List, Optional, Union
from collections import deque
'''
1254. 统计封闭岛屿的数目
二维矩阵 grid由 0（土地）和 1（水）组成。岛是由最大的4个方向连通的 0组成的群，封闭岛是一个完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
示例 1:输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]输出：2解释：灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
题眼：和“1020. 飞地的数量”是完全一样的
思路：第一步、正常访问并跟踪grid的岛屿第二步、判断跟踪的岛屿是否是 封闭的：用一个标记去跟踪遍历的岛屿（只要连通域没有在边界上即可），但是一定要把整个岛屿遍历完，不能加break提前跳出
'''class Solution:def closedIsland(self, grid: List[List[int]]) -> int:# 这道题目就是飞地的数量result = 0que = deque()m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]for i in range(m):for j in range(n):if grid[i][j] == 0 and not visited[i][j]:que.append((i, j))visited[i][j] = TrueisClose = Truewhile len(que) > 0:x, y = que.popleft()if isClose:if x == 0 or x == m-1 or y == 0 or y == n-1:isClose = Falsefor tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == 0:que.append((tx, ty))visited[tx][ty] = Trueif isClose:result += 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')grid = []for row in in_line[1].strip()[1: -1].split(']')[: -1]:grid.append([int(n) for n in row.split('[')[1].split(',')])print(obj.closedIsland(grid))except EOFError:break

130. 被围绕的区域

“1020. 飞地的数量”一样的题意，正常广度优先搜索方法基础上，额外添加 连通域内方块都预存及连通域是否为飞地的判断即可——只需要一次遍历即可

import collections
from typing import List, Optional, Union
from collections import deque
'''
130. 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1:输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的'O'都不会被填充为'X'。 任何不在边界上，或不与边界上的'O'相连的'O'最终都会被填充为'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
题眼：“1020. 飞地的数量”一样的题意，正常BFS遍历，添加上 连通域内方块都预存及连通域是否为飞地的判断即可——只需要一次遍历即可
按照这个思路改成DFS时，还是改不出来，我太菜了！
'''class Solution:def solve(self, board: List[List[str]]) -> None:# 跟“飞地的数量”是一样的题意# 用擅长的广度优先算法做吧# 情况1、矩阵为空if not board:return# 情况2、矩阵不为空que = deque()m, n = len(board), len(board[0])visited = [[False] * n for _ in range(m)]result = []for i in range(m):for j in range(n):if board[i][j] == 'O' and not visited[i][j]:que.append((i, j))visited[i][j] = Truetemp = []  # 将连通域内的所有节点都记录下来isAdd = True  # 默认连通域是飞地while len(que) > 0:x, y = que.popleft()temp.append((x, y))if isAdd:if x == 0 or x == m-1 or y == 0 or y == n-1:isAdd = Falsefor tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and board[tx][ty] == 'O':que.append((tx, ty))visited[tx][ty] = Trueif isAdd:result.append(temp)for temp in result:for x, y in temp:board[x][y] = 'X'if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]board = []for row in in_line.split(']')[: -1]:ans = []for s in row.split('[')[1].split(','):ans.append(s[1: -1])board.append(ans)obj.solve(board)print(board)except EOFError:break

1905. 统计子岛屿

有点类似于飞地（“1020. 飞地的数量”）的判断，读懂题很重要：grid2的岛屿，对应到grid1位置都为1的话，说明就是个grid1的子岛屿，正常广度优先搜索方法基础上，额外添加 对应位置到grid1中是否也都为1的判断即可

from typing import List, Optional, Union
from collections import deque
'''
1905. 统计子岛屿
给你两个m x n的二进制矩阵grid1 和grid2，它们只包含0（表示水域）和 1（表示陆地）。一个 岛屿是由 四个方向（水平或者竖直）上相邻的1组成的区域。
任何矩阵以外的区域都视为水域。如果 grid2的一个岛屿，被 grid1的一个岛屿完全 包含，也就是说 grid2中该岛屿的每一个格子都被 grid1中同一个岛屿完全包含，
那么我们称 grid2中的这个岛屿为 子岛屿。请你返回 grid2中 子岛屿的 数目。
示例 1:输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]输出：3解释：如上图所示，左边为 grid1 ，右边为 grid2 。grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
题眼：读懂题很重要：grid2的岛屿，对应到grid1位置都为1的话，说明就是个grid1的子岛屿；从这个角度看，有点类似于飞地（“1020. 飞地的数量”）的判断了
思路：第一步、正常访问并跟踪grid2的岛屿第二步、用一个标记判断跟踪的岛屿是否是 子岛屿（grid1对应位置处都是陆地就是子岛屿：gird2岛屿的正常遍历确保grid1的对应位置是一个岛屿），但是一定要把整个岛屿遍历完，不能加break提前跳出（存在可能使得剩余没有遍历的位置构成满足条件的子岛屿了）
'''class Solution:def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:# 读懂题很重要：grid2的岛屿，对应到grid1种位置都为1的话，说明就是个grid1的子岛屿# 从这个角度看，有点类似于飞地的判断了result = 0que = deque()m, n = len(grid2), len(grid2[0])visited = [[False] * n for _ in range(m)]for i in range(m):for j in range(n):if grid2[i][j] == 1 and not visited[i][j]:que.append((i, j))visited[i][j] = TrueisSub = Truewhile len(que) > 0:x, y = que.popleft()if isSub:if grid1[x][y] == 0:isSub = Falsefor tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid2[tx][ty] == 1:que.append((tx, ty))visited[tx][ty] = Trueif isSub:result += 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')grid1, grid2 = [], []for row in in_line[1].strip().split('g')[0][1: -3].split(']')[: -1]:grid1.append([int(n) for n in row.split('[')[1].split(',')])for row in in_line[2].strip()[1: -1].split(']')[: -1]:grid2.append([int(n) for n in row.split('[')[1].split(',')])print(obj.countSubIslands(grid1, grid2))except EOFError:break

695. 岛屿的最大面积

“200. 岛屿数量”的扩展，求解“连通域”的最大面积，正常广度优先搜索方法基础上，额外添加 连通域内方块个数的累计即可——只需要一次遍历即可

from typing import List, Optional, Union
from collections import deque
'''
695. 岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 
示例 1:输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]输出：6解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
题眼：“200. 岛屿数量”的扩展，求解“连通域”的最大面积，正常BFS遍历，添加上 连通域内方块个数的累计即可——只需要一次遍历即可
按照这个思路改成DFS时，觉得还是不那么好理解！
'''class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) -> int:# 广度优先搜索，在有返回值的时候，可能更好理解# 情况1、矩阵为空if not grid:return 0# 情况2、矩阵不为空que = deque()m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]result = 0for i in range(m):for j in range(n):if grid[i][j] == 1 and not visited[i][j]:que.append((i, j))visited[i][j] = Truetemp = 1while len(que) > 0:x, y = que.popleft()for tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == 1:que.append((tx, ty))visited[tx][ty] = Truetemp += 1result = max(result, temp)return result# # 深度优先搜索，在有返回值的时候，感觉并不是特别理解# # 特殊情况：矩阵为空# if not grid:#     return 0# m, n = len(grid), len(grid[0])# visited = [[False] * n for _ in range(m)]# maxArea = 0# # 搜索函数# def dfs(x, y):#     if not 0 <= x < m or not 0 <= y < n or visited[x][y] or grid[x][y] != 1:  # 非法访问、重复访问、水体#         return 0#     visited[x][y] = True#     # ans = 1#     n1 = dfs(x + 1, y)#     n2 = dfs(x - 1, y)#     n3 = dfs(x, y - 1)#     n4 = dfs(x, y + 1)#     return 1 + n1 + n2 + n3 + n4# for i in range(m):#     for j in range(n):#         if grid[i][j] == 1 and visited[i][j] == False:  # 遇到岛屿，并且是第一次访问#             area = dfs(i, j)#             maxArea = max(maxArea, area)# return maxAreaif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]grid = []for row in in_line.split(']')[:-1]:grid.append([int(i) for i in row.split('[')[1].split(',')])print(obj.maxAreaOfIsland(grid))except EOFError:break

677 · 大岛的数量

与“695. 岛屿的最大面积”差不多的一道题目，正常广度优先搜索方法基础上，额外添加 连通域内方块个数的累计即可——只需要一次遍历即可

from typing import List, Optional, Union
from collections import deque
'''
lintcode
677 · 大岛的数量
给一个布尔类型的二维数组, 0 表示海, 1 表示岛。如果两个1是相邻的,那么我们认为他们是同一个岛.我们只考虑 上下左右 相邻.
找到大小在 k 及 k 以上的岛屿的数量
示例 1:输入：[[1,1,0,0,0],[0,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,0,0,1]]2输出： 2解释：2D网络为[[1, 1, 0, 0, 0],[0, 1, 0, 0, 1],[0, 0, 0, 1, 1],[0, 0, 0, 0, 0],[0, 0, 0, 0, 1]]一共有两个大小为3的岛。
题眼：从这题 开始 统一用BFS做吧，因为DFS可能存在栈溢出，同时， 最短路径问题 也是用BFS做的，统一模板，方便记忆
思路： 
'''class Solution:def numsof_island(self, grid: List[List[int]], k: int) -> int:# 特殊情况if not grid:return 0m, n = len(grid), len(grid[0])dq = deque()  # 用BFS做result = 0visited = [[False]*n for _ in range(m)]for i in range(m):for j in range(n):if grid[i][j] == 1 and not visited[i][j]:  # 第一次被访问的岛屿dq.append((i, j))  # 加入队列，并立刻标记visited[i][j] = TruecurArea = 1while dq:  # BFSx, y = dq.popleft()for tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == 1 and not visited[tx][ty]:  # 有效、是岛屿、第一次访问dq.append((tx, ty))  # 加入队列，并立刻标记visited[tx][ty] = TruecurArea += 1if curArea >= k:result += 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip()[1: -1].split(']')[: -1]grid = []for row in in_line:grid.append([int(i) for i in row.split('[')[1].split(',')])k = int(input().strip())print(obj.numsof_island(grid, k))except EOFError:break

827. 最大人工岛

“695. 岛屿的最大面积”再加上 0变1 后的最大面积判断：需要额外添加 简单数字的岛屿标记矩阵及岛屿标记-面积哈希表

from typing import List, Optional, Union
from collections import deque
'''
827. 最大人工岛
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格0 变成1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的1 形成。
示例 1:输入: grid = [[1, 0], [0, 1]]输出: 3解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
题眼：“695. 岛屿的最大面积”再加上 0变1 后的最大面积判断：需要额外添加 简单数字的岛屿标记矩阵及岛屿标记-面积哈希表
思路：第一步，求出 岛屿面积 并对岛屿进行简单数字的标记（与哈希表的key值相同，便于直接取出value值，而不是再for循环一次），建立 岛屿标记-面积 哈希字典存储第二步，遍历0，将其变为1后，求能连接的最大岛屿面积 
'''class Solution:def largestIsland(self, grid: List[List[int]]) -> int:# 需要两次遍历，一次获取所有岛屿及其面积，二次对0变1看能连接几个岛屿——加一个岛屿标记矩阵能够在不改变原矩阵的情况下不超时# 当然，这个题直接在原矩阵中标记是最方便的，还可以省去visited矩阵# 特殊情况if not grid:return 0que = deque()m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]marked = [[-1] * n for _ in range(m)]mark_num = 0zeros = []islands = {}result = 0  # 在一次遍历中成为单个最大的岛屿for i in range(m):for j in range(n):if grid[i][j] == 0:zeros.append((i, j))elif grid[i][j] == 1 and not visited[i][j]:que.append((i, j))visited[i][j] = Truemarked[i][j] = mark_numtemp = 1  # 临时变量，统计当前岛屿面积while len(que) > 0:x, y = que.popleft()for tx, ty in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == 1:que.append((tx, ty))visited[tx][ty] = Truemarked[tx][ty] = mark_numtemp += 1islands[mark_num] = tempmark_num += 1result = max(result, temp)# 二次对0变1看能连接几个岛屿for x, y in zeros:match_keys = set()  # 避免加入重复的keyfor tx, ty in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):if 0 <= tx < m and 0 <= ty < n and marked[tx][ty] in islands:match_keys.add(marked[tx][ty])temp = 1  # 细节：加上自己，初始值设置为1for k in match_keys:temp += islands[k]result = max(result, temp)return result# 超时！# # 需要两次遍历，一次获取所有岛屿及其面积，二次对0变1看能连接几个岛屿# # 特殊情况# if not grid:#     return 0# que = deque()# m, n = len(grid), len(grid[0])# visited = [[False] * n for _ in range(m)]# zeros = []# islands = {}# result = 0  # 在一次遍历中成为单个最大的岛屿# for i in range(m):#     for j in range(n):#         if grid[i][j] == 0:#             zeros.append((i, j))#         elif grid[i][j] == 1 and not visited[i][j]:#             que.append((i, j))#             visited[i][j] = True#             key = [(i, j)]#             while len(que) > 0:#                 x, y = que.popleft()#                 for tx, ty in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):#                     if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == 1:#                         que.append((tx, ty))#                         visited[tx][ty] = True#                         key.append((tx, ty))#             islands[tuple(key)] = len(key)#             result = max(result, len(key))# # 二次对0变1看能连接几个岛屿# for x, y in zeros:#     match_keys = set()  # 避免加入重复的key#     for tx, ty in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):#         if 0 <= tx < m and 0 <= ty < n:#             for key in islands:  # 这里再套for循环取对应的岛屿标记，使得最后答案超时了#                 if (tx, ty) in key:#                     match_keys.add(key)#                     break#     temp = 1#     for k in match_keys:#         temp += islands[k]#     result = max(result, temp)# return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]grid = []for row in in_line.split(']')[: -1]:grid.append([int(i) for i in row.split('[')[1].split(',')])print(obj.largestIsland(grid))except EOFError:break

860 · 不同岛屿的个数

需要在判断岛屿个数的基础上，把相同形状的岛屿去重，也就是需要在遍历岛屿的基础上，增加hashset标记路径：相对岛屿起始点的路径：因为对矩阵的遍历总是从左上到右下的，因此相同形状的岛屿起点总是位于左上角，添加的相对路径也能对应相等，最终hashset就是岛屿个数

from typing import List, Optional, Union
from collections import deque
'''
lintcode
860 · 不同岛屿的个数
给定一个由0和1组成的非空的二维网格，一个岛屿是指四个方向（包括横向和纵向）都相连的一组1（1表示陆地）。你可以假设网格的四个边缘都被水包围。
找出所有不同的岛屿的个数。如果一个岛屿与另一个岛屿形状相同（不考虑旋转和翻折），我们认为这两个岛屿是相同的。
示例 1:输入：[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]输出：1解释：一共有两个岛，但是两个岛的形状相同输入：[[1,1,0,0,1],[1,0,0,0,0],[1,1,0,0,1],[0,1,0,1,1]]输出：3
题眼：
思路：需要在判断岛屿个数的基础上，把相同形状的岛屿去重，也就是需要在遍历岛屿的基础上，增加hashset标记路径（相对岛屿起始点的路径：因为对矩阵的遍历总是
从左上到右下的，因此相同形状的岛屿起点总是位于左上角，添加的相对路径也能对应相等），最终hashset就是岛屿个数
'''class Solution:def numberof_distinct_islands(self, grid: List[List[int]]) -> int:# 特殊情况if not grid:return 0m, n = len(grid), len(grid[0])dq = deque()  # 用BFS做island = set()  # set自动去重visited = [[False]*n for _ in range(m)]for i in range(m):for j in range(n):path = []if grid[i][j] == 1 and not visited[i][j]:  # 第一次被访问的岛屿dq.append((i, j))  # 加入队列，并立刻标记visited[i][j] = Truepath.append(str((i-i, j-j)))  # 路径添加相对岛屿起点的坐标位置：用元组作为集合内元素也可以while dq:  # BFSx, y = dq.popleft()for tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == 1 and not visited[tx][ty]:  # 有效、是岛屿、第一次访问dq.append((tx, ty))  # 加入队列，并立刻标记visited[tx][ty] = Truepath.append(str((tx-i, ty-j)))  # 路径添加相对岛屿起点的坐标位置island.add(''.join(path))return len(island)if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip()[1: -1].split(']')[: -1]grid = []for row in in_line:grid.append([int(i) for i in row.split('[')[1].split(',')])print(obj.numberof_distinct_islands(grid))except EOFError:break

804 · 不同岛屿的个数II

需要在判断岛屿个数的基础上，把相同形状（加上旋转和翻转，一共8种）的岛屿去重；对于每个形状的岛屿，都把原始位置添加上，经过正则函数返回该岛屿形状对应的唯一标识，正则函数逻辑：添加该形状的8种旋转、翻转变化，然后对每种形状各自排序后取最小值（排序这个逻辑不是很理解）

from typing import List, Optional, Union
from collections import deque
'''
lintcode
804 · 不同岛屿的个数II
给定一个由0和1组成的非空的二维网格，一个岛屿是指四个方向（包括横向和纵向）都相连的一组1（1表示陆地）。你可以假设网格的四个边缘都被水包围。
计算不同岛屿的数量。当一个岛被认为与另一个岛相同时，它们有相同的形状，或在旋转后的形状相同(90,180，或270度)或翻转(左/右方向或向上/向下方向)。
示例 1:输入：[[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]输出：1解释：一共有两个岛，但是两个岛旋转后的形状相同
题眼：
思路：需要在判断岛屿个数的基础上，把相同形状（加上旋转和翻转，一共8种）的岛屿去重；对于每个形状的岛屿，都把原始位置添加上，经过正则函数返回该岛屿形状
对应的唯一标识，正则函数逻辑：添加该形状的8种旋转、翻转变化，然后对每种形状各自排序后取最小值（排序这个逻辑不是很理解）
'''class Solution:def num_distinct_islands2(self, grid: List[List[int]]) -> int:# 特殊情况if not grid:return 0m, n = len(grid), len(grid[0])dq = deque()  # 用BFS做island = set()  # set自动去重visited = [[False]*n for _ in range(m)]for i in range(m):for j in range(n):shape = []if grid[i][j] == 1 and not visited[i][j]:  # 第一次被访问的岛屿dq.append((i, j))  # 加入队列，并立刻标记visited[i][j] = Trueshape.append((i, j))  # 添加岛屿的第一个位置while dq:  # BFSx, y = dq.popleft()for tx, ty in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == 1 and not visited[tx][ty]:  # 有效、是岛屿、第一次访问dq.append((tx, ty))  # 加入队列，并立刻标记visited[tx][ty] = Trueshape.append((tx, ty))  # 添加岛屿的其他位置island.add(self.canonical(shape))  # 添加正则化后的岛屿return len(island)def canonical(self, shape):  # 这一部分老是写不对def encode(shape):x, y = shape[0]return "".join(str(i - x) + ':' + str(j - y) for i, j in shape)  # 减去起始点取相对位置是对排序后的形状进行的shapes = [[(a * i, b * j) for i, j in shape] for a, b in ((1, 1), (1, -1), (-1, 1), (-1, -1))]  # 添加 翻转shapes += [[(j, i) for i, j in shape] for shape in shapes]  # 添加 旋转return min(encode(sorted(shape)) for shape in shapes)  # 返回排序后的结果if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip()[1: -1].split(']')[: -1]grid = []for row in in_line:grid.append([int(i) for i in row.split('[')[1].split(',')])print(obj.num_distinct_islands2(grid))except EOFError:break