Leetcode刷题笔记1 图论part03

卡码网 101 孤岛总面积

from collections import deque
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
count = 0def main():global countn, m = map(int, input().split())grid = []for _ in range(n):grid.append(list(map(int, input().split())))for i in range(n):if grid[i][0] == 1:dfs(grid, i, 0)if grid[i][m - 1] == 1:dfs(grid, i, m - 1)for j in range(m):if grid[0][j] == 1:dfs(grid, 0, j)if grid[n - 1][j] == 1:dfs(grid, n - 1, j)count = 0for i in range(n):for j in range(m):if grid[i][j] == 1:dfs(grid, i, j)print(count)def dfs(grid, i, j):que = deque()global countque.append((i, j))grid[i][j] = 0count += 1while que:cur_x, cur_y = que.popleft()for x, y in directions:next_x, next_y = cur_x + x, cur_y + yif next_x < 0 or next_y < 0 or next_x >= len(grid) or next_y >= len(grid[0]):continueif grid[next_x][next_y] == 1:count += 1que.append((next_x, next_y))grid[next_x][next_y] = 0if __name__ == '__main__':main()

卡码网 102 沉没孤岛

from collections import dequen, m = list(map(int, input().split()))
g = []
for _ in range(n):row = list(map(int,input().split()))g.append(row)directions = [(1,0),(-1,0),(0,1),(0,-1)]
count = 0def bfs(r,c,mode):global count q = deque()q.append((r,c))count += 1while q:r, c = q.popleft()if mode:g[r][c] = 2for di in directions:next_r = r + di[0]next_c = c + di[1]if next_c < 0 or next_c >= m or next_r < 0 or next_r >= n:continueif g[next_r][next_c] == 1:q.append((next_r,next_c))if mode:g[r][c] = 2count += 1for i in range(n):if g[i][0] == 1: bfs(i,0,True)if g[i][m-1] == 1: bfs(i, m-1,True)for j in range(m):if g[0][j] == 1: bfs(0,j,1)if g[n-1][j] == 1: bfs(n-1,j,1)for i in range(n):for j in range(m):if g[i][j] == 2:g[i][j] = 1else:g[i][j] = 0for row in g:print(" ".join(map(str, row)))

卡码网 103 水流问题

first = set()
second = set()
directions = [[0, 1], [1, 0], [0 ,-1], [-1, 0]]
def dfs(i, j, grid, visited, side):if visited[i][j]:returnvisited[i][j] = Trueside.add((i, j))for x, y in directions:new_x = i + x new_y = j + yif (0 <= new_x < len(grid)and 0 <= new_y < len(grid[0])and int(grid[new_x][new_y]) >= int(grid[i][j])):dfs(new_x, new_y, grid, visited, side)def main():global firstglobal secondn, m = map(int, input().split())grid = []for _ in range(n):grid.append(list(map(int, input().strip().split())))visited = [[False] * m for _ in range(n)]for i in range(m):dfs(0, i, grid, visited, first)for i in range(n):dfs(i, 0, grid, visited, first)visited = [[False] * m for _ in range(n)]for i in range(m):dfs(n - 1, i, grid, visited, second)for i in range(n):dfs(i, m - 1, grid, visited, second)res = first & secondfor x, y in res:print(f"{x} {y}")if __name__ == '__main__':main()

卡码网 104 建造最大岛屿

from typing import List 
from collections import defaultdictclass Solution():def __init__(self):self.direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]self.res = 0self.count = 0self.idx = 1self.count_area = defaultdict(int)def max_area_island(self, grid: List[List[int]]) -> int:if not grid or len(grid) == 0 or len(grid[0]) == 0:return 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:self.count = 0self.idx += 1self.dfs(grid, i, j)self.check_area(grid)if self.check_largest_connnect_island(grid):return self.res + 1return max(self.count_area.values())def dfs(self, grid, x, y):grid[x][y] = self.idxself.count += 1for i, j in self.direction:next_x = x + inext_y = y + jif 0 <= next_x < len(grid) and 0 <= next_y < len(grid[0]) and grid[next_x][next_y] == 1:self.dfs(grid, next_x, next_y)returndef check_area(self, grid):for i in range(len(grid)):for j in range(len(grid[0])):self.count_area[grid[i][j]] = self.count_area.get(grid[i][j], 0) + 1returndef check_largest_connnect_island(self, grid):m, n = len(grid), len(grid[0])has_connect = Falsefor i in range(m):for j in range(n):if grid[i][j] == 0:has_connect = Truearea = 0visited = set()for x, y in self.direction:next_x = x + inext_y = y + jif 0 <= next_x < len(grid) and 0 <= next_y < len(grid[0]) and grid[next_x][next_y] != 0 and grid[next_x][next_y] not in visited:visited.add(grid[next_x][next_y])area += self.count_area[grid[next_x][next_y]]self.res = max(self.res, area)return has_connectdef main():n, m = map(int, input().split())grid = []for _ in range(n):grid.append(list(map(int, input().strip().split())))sol = Solution()print(sol.max_area_island(grid))
if __name__ == '__main__':main()