Untitled
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