LCP 75. 传送卷轴
二分 + dfs
细节很多。。建议自己再写一遍
灵茶山
class Solution:
def challengeOfTheKeeper(self, maze: List[str]) -> int:
inf = int(1e9)
n, m = len(maze), len(maze[0])
for i in range(n):
for j in range(m):
if maze[i][j] == 'S':
sx, sy = i, j
if maze[i][j] == 'T':
tx, ty = i, j
dist = [[inf] * m for _ in range(n)]
dist[tx][ty] = 0
q = [(tx, ty)]
step = 1
while q:
tmp = q
q = []
for i, j in tmp:
for x, y in (i + 1, j) , (i - 1, j), (i, j - 1), (i, j + 1):
if 0 <= x and x < n and 0 <= y and y < m and dist[x][y] == inf and maze[x][y] != '#':
dist[x][y] = step
q.append((x, y))
step += 1
# print(dist)
if dist[sx][sy] == inf:
return -1
# print(n, m)
def check(max_dis):
visit = set()
def dfs(i, j):
if i < 0 or i >= n or j < 0 or j >= m or maze[i][j] == '#' or (i, j) in visit:
return False
if maze[i][j] == 'T':
return True
if maze[i][j] == '.':
if maze[i][m - j - 1] != '#' and dist[i][m - j - 1] > max_dis:
return False
if maze[n - i - 1][j] != '#' and dist[n - i - 1][j] > max_dis:
return False
visit.add((i, j))
for x, y in (i + 1, j) , (i - 1, j), (i, j - 1), (i, j + 1):
if dfs(x, y):
return True
return False
return dfs(sx, sy)
l, r = 0, m * n + 1
while l < r:
mid = (l + r) // 2
if check(mid):
r = mid
else:
l = mid + 1
if l >= m * n:
return -1
return l
