# 最短路径

描述

给出一个二维的表格图，其中每个格子上有一个数字 `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里，会把结果滤掉

```python
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          
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2024/zui-duan-lu-jing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.