# Untitled

unknown
plain_text
a month ago
1.8 kB
1
Indexable
Never
```def findBestPath(n, m, startRow, startColumn, endRow, endColumn, monsterRow, monsterColumn):
def distance(x1, y1, x2, y2):
return abs(x1 - x2) + abs(y1 - y2)

def bfs(x, y):
visited = [[False] * m for _ in range(n)]
queue = [(x, y, 0)]
visited[x][y] = True

while queue:
curr_x, curr_y, dist = queue.pop(0)

for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_x, new_y = curr_x + dx, curr_y + dy

if 0 <= new_x < n and 0 <= new_y < m and not visited[new_x][new_y]:
visited[new_x][new_y] = True
queue.append((new_x, new_y, dist + 1))
min_dist[new_x][new_y] = dist + 1

min_dist = [[float('inf')] * m for _ in range(n)]
min_dist[startRow][startColumn] = 0

for i in range(len(monsterRow)):
bfs(monsterRow[i], monsterColumn[i])

left, right = 0, distance(startRow, startColumn, endRow, endColumn)
result = 0

while left <= right:
mid = (left + right) // 2
dp = [[False] * m for _ in range(n)]
dp[startRow][startColumn] = True
queue = [(startRow, startColumn)]

while queue:
curr_x, curr_y = queue.pop(0)

for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_x, new_y = curr_x + dx, curr_y + dy

if 0 <= new_x < n and 0 <= new_y < m and not dp[new_x][new_y] and min_dist[new_x][new_y] >= mid:
dp[new_x][new_y] = True
queue.append((new_x, new_y))

if dp[endRow][endColumn]:
result = mid
left = mid + 1
else:
right = mid - 1

return result```