题解 | #portal#

两次bfs求出起点与终点到传送门的距离,之后枚举传送门的放置地点即可

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最终要输出的答案
# @param N int整型 表示地图的大小
# @param a int整型二维数组 地图的描述
# @return int整型
#
class Solution:
    def solve(self , N , a ):
        # write code here
        dir_ = {(0,1),(1,0),(0,-1),(-1,0)}
        trans = []
        spe_x,spe_y = -1,-1
        dis = {(0,0):0}
        queue = [(0,0,0)]
        visited = {(0,0)}
        while queue:
            x,y,d = queue.pop(0)
            for dx,dy in dir_:
                if x + dx < 0 or x + dx >= N or y + dy < 0 or y + dy >= N or (x + dx,y + dy) in visited or a[x + dx][y + dy] == 1:
                    continue
                if a[x + dx][y + dy] == 3:
                    spe_x,spe_y = x + dx,y + dy
                else:
                    if a[x + dx][y + dy] == 2:
                        trans.append((x + dx,y + dy))
                visited.add((x + dx,y + dy))
                dis[(x + dx,y + dy)] = d + 1
                queue.append((x + dx,y + dy,d + 1))

        ans = dis[(N - 1,N - 1)]
        if len(trans) == 0:
            return ans

        re_dis = {(N - 1,N - 1):0}
        visited.clear()
        queue.clear()
        queue.append((N - 1,N - 1,0))
        visited.add((N - 1,N - 1))

        while queue:
            x,y,d = queue.pop(0)
            for dx,dy in dir_:
                if x + dx < 0 or x + dx >= N or y + dy < 0 or y + dy >= N or (x + dx,y + dy) in visited or a[x + dx][y + dy] == 1:
                    continue
                visited.add((x + dx,y + dy))
                re_dis[(x + dx,y + dy)] = d + 1
                queue.append((x + dx,y + dy,d + 1))

        for x,y in trans:
            ans = min(ans,dis[(x,y)] + re_dis[(spe_x,spe_y)] + 1,dis[(spe_x,spe_y)] + re_dis[(x,y)] + 1)
        return ans