[LeetCode]The Maze II

又是图的问题，找最短路径。这道题用Dijkstra就行，Dijkstra其实就是每条边带权重的BFS，和不带权重的BFS的区别就是，Dijkstra用的是priority queue，并且最短路径是在从priority queue取下节点展开的时候获得（第一次见到不一定是最短路径，还有可能继续更新），而不带权重的BFS在我们第一次见到目标节点的时候最短路径就找到了。具体算法和证明就不在这细讲，这是比较熟悉的算法了。这道题不需要事先建图，因为每一步我们可以找到相邻的节点。如果是找所有点到起点的最短路径，我们用map来记录是否展开和最短路径，如果只是找一个点，用set来记录是否展开过就行，类似BFS，代码如下：