130. Surrounded Regions 417. Pacific Atlantic Water Flow
Given an?m x n?matrix?board?containing?'X'?and?'O',?capture all regions that are 4-directionally?surrounded by?'X'.
A region is?captured?by flipping all?'O's into?'X's in that surrounded region.
Mark all the 'O' islands near the edges with 'A' , then traverse the whole map, and if we?come across an 'O' that hasn't been marked, then just change it to an 'X'.
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
m = len(board)
n = len(board[0])
self.visited = [[False] * n for _ in range(m)]
self.dirs = [(1,0),(-1,0),(0,1),(0,-1)]
for i in range(m):
self.dfs(board, i, 0)
self.dfs(board, i, n -1)
for j in range(n):
self.dfs(board, 0, j)
self.dfs(board, m - 1, j)
for i in range(m):
for j in range(n):
if not self.visited[i][j] and board[i][j] == "O":
board[i][j] = "X"
for i in range(m):
self.dfs(board, i, 0)
self.dfs(board, i, n -1)
for j in range(n):
self.dfs(board, 0, j)
self.dfs(board, m - 1, j)
def dfs(self, board, x, y):
if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or self.visited[x][y] or board[x][y] == "X":
return
self.visited[x][y] = True
if board[x][y] == "O":
board[x][y] = "A"
if board[x][y] == "A":
board[x][y] = "O"
for _dir in self.dirs:
self.dfs(board, x + _dir[0], y + _dir[1])417. Pacific Atlantic Water Flow
There is an?m x n?rectangular island that borders both the?Pacific Ocean?and?Atlantic Ocean. The?Pacific Ocean?touches the island's left and top edges, and the?Atlantic Ocean?touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an?m x n?integer matrix?heights?where?heights[r][c]?represents the?height above sea level?of the cell at coordinate?(r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is?less than or equal to?the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return?a?2D list?of grid coordinates?result?where?result[i] = [ri, ci]?denotes that rain water can flow from cell?(ri, ci)?to?both?the Pacific and Atlantic oceans.
It is possible to start from the edge of the Pacific and the Atlantic and mark the cells that are reachable from both oceans.
Finally, it is enough to find the coordinates of the grid where both can be reached.
Time complexity: O(m x n)
Space complexity: O(m x n)
DFS:
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m = len(heights)
n = len(heights[0])
self.dirs = [(1,0), (-1,0), (0,1), (0, -1)]
self.ans_1 = [[0] * n for _ in range(m)]
self.ans_2 = [[0] * n for _ in range(m)]
result = []
for i in range(m):
self.dfs_1(heights, i, 0)
self.dfs_2(heights, i, n - 1)
for j in range(n):
self.dfs_1(heights, 0, j)
self.dfs_2(heights, m - 1, j)
for i in range(m):
for j in range(n):
if self.ans_1[i][j] and self.ans_2[i][j]:
result.append([i,j])
return result
def dfs_1(self, heights, x, y):
if not self.ans_1[x][y]:
self.ans_1[x][y] = 1
for _dir in self.dirs:
x1 = x + _dir[0]
y1 = y + _dir[1]
if 0 <= x1 < len(heights) and 0 <= y1 < len(heights[0]) and heights[x][y] <= heights[x1][y1]:
self.dfs_1(heights, x1, y1)
def dfs_2(self, heights, x, y):
if not self.ans_2[x][y]:
self.ans_2[x][y] = 1
for _dir in self.dirs:
x1 = x + _dir[0]
y1 = y + _dir[1]
if 0 <= x1 < len(heights) and 0 <= y1 < len(heights[0]) and heights[x][y] <= heights[x1][y1]:
self.dfs_2(heights, x1, y1)simplified:
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m,n=len(heights),len(heights[0])
res=[]
pacific = [[False]*n for _ in range(m)]
atlantic = [[False]*n for _ in range(m)]
for i in range(m):
self.DFS(i,0,pacific,heights)
self.DFS(i,n-1,atlantic,heights)
for j in range(n):
self.DFS(0,j,pacific,heights)
self.DFS(m-1,j,atlantic,heights)
for i in range(m):
for j in range(n):
if pacific[i][j] and atlantic[i][j]:
res.append([i,j])
return res
def DFS(self,i,j,visited,heights):
if visited[i][j]:
return
visited[i][j]=True
directions = [(0,1),(0,-1),(1,0),(-1,0)]
for step_i,step_j in directions:
new_i,new_j=i+step_i,j+step_j
if 0<=new_i<len(heights) and 0<=new_j<len(heights[0]) and heights[new_i][new_j]>=heights[i][j]:
self.DFS(new_i,new_j,visited,heights)?
BFS:
class Solution:
def __init__(self):
self.position = [[-1, 0], [0, 1], [1, 0], [0, -1]]
# heights：题目给定的二维数组，visited：记录这个位置可以到哪条河
def bfs(self, heights: List[List[int]], queue: deque, visited: List[List[List[int]]]):
while queue:
curPos = queue.popleft()
for current in self.position:
row, col, sign = curPos[0] + current[0], curPos[1] + current[1], curPos[2]
# 越界
if row < 0 or row >= len(heights) or col < 0 or col >= len(heights[0]): continue
# 不满足条件或已经访问过
if heights[row][col] < heights[curPos[0]][curPos[1]] or visited[row][col][sign]: continue
visited[row][col][sign] = True
queue.append([row, col, sign])
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rowSize, colSize = len(heights), len(heights[0])
# visited 记录 [row, col] 位置是否可以到某条河，可以为 true，反之为 false；
# 假设太平洋的标记为 1，大西洋为 0
# ans 用来保存满足条件的答案
ans, visited = [], [[[False for _ in range(2)] for _ in range(colSize)] for _ in range(rowSize)]
# 队列，保存的数据为 [行号, 列号, 标记]
# 假设太平洋的标记为 1，大西洋为 0
queue = deque()
for row in range(rowSize):
visited[row][0][1] = True
visited[row][colSize - 1][0] = True
queue.append([row, 0, 1])
queue.append([row, colSize - 1, 0])
for col in range(0, colSize):
visited[0][col][1] = True
visited[rowSize - 1][col][0] = True
queue.append([0, col, 1])
queue.append([rowSize - 1, col, 0])
self.bfs(heights, queue, visited) # 广度优先遍历
for row in range(rowSize):
for col in range(colSize):
# 如果该位置即可以到太平洋又可以到大西洋，就放入答案数组
if visited[row][col][0] and visited[row][col][1]:
ans.append([row, col])
return ans本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！