day52-graph theory-part03-8.23

1. 101.孤岛总面积

pay attention to the requirement, it is not calculating the total area, instead, it is required to claculate the islands area which do not have edges touching the sides.

here, we use a boolen variable to track if the area is an island which linked to the edge. This varibale is used to decide if the area would be calculated into the final result.

direction = [[0,1],[0,-1],[1,0],[-1,0]]def dfs(graph, visited, x, y, area, if_touch):if x == 0 or x == len(graph)-1 or y == 0 or y == len(graph[0])-1:if_touch = Truefor dirx, diry in direction:searchx = x + dirxsearchy = y + diryif searchx < 0 or searchx >= len(graph) or searchy < 0 or searchy >= len(graph[0]):continueif graph[searchx][searchy] == 1 and not visited[searchx][searchy]:area += 1visited[searchx][searchy] = Truearea, if_touch = dfs(graph, visited, searchx, searchy, area, if_touch)return area, if_touchdef main():n, m = map(int, input().split())graph = []for i in range(n):graph.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]result = 0for i in range(n):for j in range(m):if graph[i][j] == 1 and not visited[i][j]:if_touch = Falsearea = 0area += 1visited[i][j] = Truearea, if_touch = dfs(graph, visited, i, j, area, if_touch)if if_touch == False:result += area# print(i, j, area)print(result)if __name__ == "__main__":main()

2. 102.沉默孤岛

In this practice, because the requirement is doing modification onto the map, so the operation should be done along with the dfs process.

changing these island to 2, preserve the isolated island as 1, then reduce 2 to 1, while 1 to 0

direction = [[0,1],[0,-1],[1,0],[-1,0]]def dfs(graph, x, y):graph[x][y] = 2for dirx, diry in direction:searchx = x + dirxsearchy = y + diryif searchx < 0 or searchx >= len(graph) or searchy < 0 or searchy >= len(graph[0]):continueif graph[searchx][searchy] == 0 or graph[searchx][searchy] == 2:continuedfs(graph, searchx, searchy)returndef main():n, m = map(int, input().split())graph = []for _ in range(n):graph.append(list(map(int, input().split())))for i in range(n):if graph[i][0] == 1: dfs(graph, i, 0)if graph[i][m-1] == 1: dfs(graph, i, m-1)for j in range(m):if graph[0][j] == 1: dfs(graph, 0, j)if graph[n-1][j] == 1: dfs(graph, n-1, j)for i in range(n):for j in range(m):if graph[i][j] == 2: graph[i][j] = 1elif graph[i][j] == 1: graph[i][j] = 0for i in range(n):print(' '.join(list(map(str,graph[i]))))if __name__ == "__main__":main()

3. 103.水流问题

This practice takes a reverse mindset, search from sides, then see which point can be both searched by two kinds of sides.

direction = [[0,1],[0,-1],[1,0],[-1,0]]def dfs(graph, visited, x, y):if visited[x][y]:returnvisited[x][y] = Truefor dirx, diry in direction:searchx = x + dirxsearchy = y + diry# print(x, y, searchx, searchy, len(graph), len(graph[0]))if searchx < 0 or searchx >= len(graph) or searchy < 0 or searchy >= len(graph[0]):continueif graph[searchx][searchy] < graph[x][y]:continuedfs(graph, visited, searchx, searchy)returndef main():n, m = map(int, input().split())graph = []for _ in range(n):graph.append(list(map(int, input().split())))visited_1 = [[False] * m for _ in range(n)]visited_2 = [[False] * m for _ in range(n)]for i in range(n):dfs(graph, visited_1, i, 0)dfs(graph, visited_2, i, m-1)for j in range(m):dfs(graph, visited_1, 0, j)dfs(graph, visited_2, n-1, j)result = []for i in range(n):for j in range(m):if visited_1[i][j] and visited_2[i][j]:result.append([i,j])print(' '.join([str(i), str(j)]))if __name__ == "__main__":main()

4. 104.建造最大岛屿

from collections import defaultdict
direction = [[0,1],[0,-1],[1,0],[-1,0]]def dfs(graph, visited, x, y, area, mark):for dirx, diry in direction:searchx = x + dirxsearchy = y + diryif searchx < 0 or searchy >= len(graph) or searchy < 0 or searchy >= len(graph[0]):continueif graph[searchx][searchy] == 1 and not visited[searchx][searchy]:area += 1graph[searchx][searchy] = markvisited[searchx][searchy] = Truearea = dfs(graph, visited, searchx, searchy, area, mark)return areadef main():n, m = map(int, input().split())graph = []for _ in range(n):graph.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]mark = 2gridArea = defaultdict(int)for i in range(n):for j in range(m):if graph[i][j] == 1 and not visited[i][i]:visited[i][j] = Truegraph[i][j] = markarea = 1area = dfs(graph, visited, i, j, area, mark)gridArea[mark] = areamark += 1countIsland = set()result = 0for i in range(n):for j in range(m):if graph[i][j] == 0:newarea = 1for x, y in direction:newx = x + inewy = y + jif graph[newx][newy] in countIsland: continuenewarea += gridArea[graph[newx][newy]]countIsland.add(graph[newx][newy])result = max(result, newarea)print(result)if __name__ == "__main__":main()