代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域

代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域

---

---

65.岛屿的最大面积

题目链接

一、BFS

class Solution(object):def maxAreaOfIsland(self, grid):""":type grid: List[List[int]]:rtype: int"""# BFSm,n = len(grid),len(grid[0])visited = [[False]*n for _ in range(m)]dirs = [(-1,0),(0,1),(1,0),(0,-1)]maxres = 0def bfs(i,j):q = collections.deque()q.append((i,j))visited[i][j]=Truecount=1while q:x,y = q.popleft()for d in dirs:nextx = x+d[0]nexty = y+d[1]if nextx<0 or nextx>=m or nexty<0 or nexty>=n:continueif visited[nextx][nexty] or grid[nextx][nexty]==0:continueq.append((nextx,nexty))visited[nextx][nexty]=Truecount +=1return countfor i in range(m):for j in range(n):if not visited[i][j] and grid[i][j]==1:count = bfs(i,j)maxres = max(maxres,count)return maxres

二、DFS

class Solution(object):def maxAreaOfIsland(self, grid):""":type grid: List[List[int]]:rtype: int"""# DFSm,n = len(grid),len(grid[0])visited = [[False]*n for _ in range(m)]dirs = [(-1,0),(0,1),(1,0),(0,-1)]result = 0def dfs(x,y):count = 1for d in dirs:nextx = x+d[0]nexty = y+d[1]if nextx>=m or nextx<0 or nexty>=n or nexty<0:continueif visited[nextx][nexty] or grid[nextx][nexty]==0:continuevisited[nextx][nexty]=Trueres = dfs(nextx,nexty)count += resreturn countfor i in range(m):for j in range(n):if not visited[i][j] and grid[i][j]==1:visited[i][j]=Truecount = dfs(i,j)result = max(result,count)return result

---

1020.飞地的数量

题目链接

一、DFS

class Solution(object):def numEnclaves(self, grid):m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]def dfs(x, y):visited[x][y] = True# grid[x][y] = 2  # Mark as visited by changing the value to 2for d in dirs:nextx, nexty = x + d[0], y + d[1]if 0 <= nextx < m and 0 <= nexty < n and not visited[nextx][nexty] and grid[nextx][nexty] == 1:dfs(nextx, nexty)for i in range(m):for j in [0, n-1]:  # Only left and right bordersif grid[i][j] == 1 and not visited[i][j]:dfs(i, j)for j in range(n):for i in [0, m-1]:  # Only top and bottom bordersif grid[i][j] == 1 and not visited[i][j]:dfs(i, j)# Count cells that are still 1 (enclaves)res = 0for i in range(m):for j in range(n):if grid[i][j] == 1 and not visited[i][j]:res += 1return res

二、BFS

class Solution(object):def numEnclaves(self, grid):m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]# BFSdef bfs(x,y):q = collections.deque()q.append((x,y))while q:x,y = q.popleft()for d in dirs:nextx = x+d[0]nexty = y+d[1]if 0<= nextx <m and 0<=nexty<n and visited[nextx][nexty]==False and grid[nextx][nexty]==1:q.append((nextx,nexty))visited[nextx][nexty]=Truefor i in range(m):for j in [0,n-1]:if visited[i][j]==False and grid[i][j]==1:visited[i][j]=Truebfs(i,j)for j in range(n):for i in [0,m-1]:if visited[i][j]==False and grid[i][j]==1:visited[i][j]=Truebfs(i,j)# Count cells that are still 1 (enclaves)res = 0for i in range(m):for j in range(n):if grid[i][j] == 1 and not visited[i][j]:res += 1return res

三、本题总结

其实就是从边缘遍历，不是整幅图遍历，最后边缘能遍历到的就都visited=True了，剩下的False且为陆地的就是飞地。

---

130.被围绕的区域

题目链接

一、DFS

class Solution(object):def solve(self, board):""":type board: List[List[str]]:rtype: None Do not return anything, modify board in-place instead."""# DFSm, n = len(board), len(board[0])dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]# DFSdef dfs(x, y):board[x][y] = 'A'  # Mark as visited by changing the value to 2for d in dirs:nextx, nexty = x + d[0], y + d[1]if 0 <= nextx < m and 0 <= nexty < n  and board[nextx][nexty] == 'O':dfs(nextx, nexty)for i in range(m):for j in [0, n-1]:  # Only left and right bordersif board[i][j] == 'O' :dfs(i, j)for j in range(n):for i in [0, m-1]:  # Only top and bottom bordersif board[i][j] == 'O' :dfs(i, j)for i in range(m):for j in range(n):if board[i][j] == 'O' :board[i][j]='X'if board[i][j]=='A':board[i][j]='O'return board