代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域
文章目录
65.岛屿的最大面积
一、BFS
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# BFS
m,n = len(grid),len(grid[0])
visited = [[False]*n for _ in range(m)]
dirs = [(-1,0),(0,1),(1,0),(0,-1)]
maxres = 0
def bfs(i,j):
q = collections.deque()
q.append((i,j))
visited[i][j]=True
count=1
while 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:
continue
if visited[nextx][nexty] or grid[nextx][nexty]==0:
continue
q.append((nextx,nexty))
visited[nextx][nexty]=True
count +=1
return count
for 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
"""
# DFS
m,n = len(grid),len(grid[0])
visited = [[False]*n for _ in range(m)]
dirs = [(-1,0),(0,1),(1,0),(0,-1)]
result = 0
def dfs(x,y):
count = 1
for d in dirs:
nextx = x+d[0]
nexty = y+d[1]
if nextx>=m or nextx<0 or nexty>=n or nexty<0:
continue
if visited[nextx][nexty] or grid[nextx][nexty]==0:
continue
visited[nextx][nexty]=True
res = dfs(nextx,nexty)
count += res
return count
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j]==1:
visited[i][j]=True
count = 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 2
for 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 borders
if 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 borders
if grid[i][j] == 1 and not visited[i][j]:
dfs(i, j)
# Count cells that are still 1 (enclaves)
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and not visited[i][j]:
res += 1
return 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)]
# BFS
def 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]=True
for i in range(m):
for j in [0,n-1]:
if visited[i][j]==False and grid[i][j]==1:
visited[i][j]=True
bfs(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]=True
bfs(i,j)
# Count cells that are still 1 (enclaves)
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and not visited[i][j]:
res += 1
return 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.
"""
# DFS
m, n = len(board), len(board[0])
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# DFS
def dfs(x, y):
board[x][y] = 'A' # Mark as visited by changing the value to 2
for 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 borders
if board[i][j] == 'O' :
dfs(i, j)
for j in range(n):
for i in [0, m-1]: # Only top and bottom borders
if 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
