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