最短路径

https://www.lintcode.com/problem/1364/solution?utm_source=sc-libao-ql

描述

给出一个二维的表格图，其中每个格子上有一个数字 num。

如果 num 是 -2 表示这个点是起点，num 是 -3 表示这个点是终点，num 是 -1 表示这个点是障碍物不能行走，num 为 0 表示这个点是道路可以正常行走。

如果 num 是正数，表示这个点是传送门，则这个点可以花费 1 的代价到达有着相同数字的传送门格子中。

每次可以花费 1 的代价向上下左右四个方向之一行走一格，传送门格子也可以往四个方向走求出从起点到终点的最小花费，如果不能到达返回 -1。

图最大是400*400的;

传送门的种类不会超过50; 即图中最大正数不会超过50

样例

输入：[[1,0,-1,1],[-2,0,-1,-3],[2,2,0,0]]输出：3解释：从-2起点先向上走到1，再通过传送门到达最右上角的1位置 再往下走到达-3终点

分析

bfs

1. 这里除了四周的点，还要加入可以跳转的点，也就是portal

2. 注意每次加完Portal的List,要清除，防止重复跳转

3. python dict赋值，不要用get(key,defualt)，因为无法赋值

4. 不要重复查点在不在distance里，会把结果滤掉

from typing import (
    List,
)
from collections import deque
class Solution:
    """
    @param maze_map: a 2D grid
    @return: return the minium distance
    """
    def get_min_distance(self, maze_map: List[List[int]]) -> int:
        # write your code here
        if not maze_map:
            return 0
        n,m = len(maze_map), len(maze_map[0])
        q = deque()
        directions = [(1,0),(0,1),(-1,0),(0,-1)]
        distance = {}
        num_dict = {}
        for i in range(n):
            for j in range(m):
                if maze_map[i][j] == -2:
                    q.append((i,j))
                    distance[(i,j)] = 0
                if maze_map[i][j] > 0:
                    if maze_map[i][j] not in num_dict:
                        num_dict[maze_map[i][j]] = []
                    num_dict[maze_map[i][j]].append((i,j))

        while q:
            x,y = q.popleft()
            if maze_map[x][y] == -3:
                return distance[(x,y)]

            for dx,dy in directions:
                nx,ny = x+dx,y+dy
                if 0 <= nx < n and 0 <= ny < m and maze_map[nx][ny] != -1 and (nx,ny) not in distance:
                        distance[(nx,ny)] = distance[(x,y)] + 1   
                        q.append((nx, ny))    

            if maze_map[x][y] > 0:     
                for nx,ny in num_dict[maze_map[x][y]]:
                    if (nx,ny) not in distance:
                        distance[(nx,ny)] = distance[(x,y)] + 1 
                        q.append((nx, ny)) 
                num_dict[maze_map[x][y]] = [] #防止重复处理    

        return -1