关键词排行优化网站,网站如何提升用户体验,学校网站需求,开发手机网站制作代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域 文章目录 代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域65.岛屿的最大面积一、BFS二、DFS 1020.飞地的数量一、DFS…代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域 文章目录 代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域65.岛屿的最大面积一、BFS二、DFS 1020.飞地的数量一、DFS二、BFS三、本题总结 130.被围绕的区域一、DFS 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]Truecount1while q:x,y q.popleft()for d in dirs:nextx xd[0]nexty yd[1]if nextx0 or nextxm or nexty0 or nextyn: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 xd[0]nexty yd[1]if nextxm or nextx0 or nextyn or nexty0: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 result1020.飞地的数量
题目链接
一、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 xd[0]nexty yd[1]if 0 nextx m and 0nextyn 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三、本题总结
其实就是从边缘遍历不是整幅图遍历最后边缘能遍历到的就都visitedTrue了剩下的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]Xif board[i][j]A:board[i][j]Oreturn board
