1091.二维矩阵中的最短路径

题目思路：
使用dijkstra算法，因为题目的特殊性，没有必要严格按照dijkstra去执行，可以适当简化，比如我这里并没有设计bool数组去标记S集和U集，因为没必要。也没有用优先队列去装距离。

复习dijkstra算法：
算法目的：
求得 单个定点 到 其余各个点的最短距离
算法步骤：
1.设计S集、U集，S中放已经找到最短路径的点，U集放尚未处理的点
2.设计3个状态集合，dist和useddist存储当前已经找到的从单个定点到其余各个点的最小距离（算法没执行完的话，不一定是最小距离，执行完之后才是），used[i]存储是否已经处理完第i个节点，用来区分是S集还是U集。
3.每次从U集中取出从 单个定点 到U集中的点 路径最短的点，然后以该点为中间节点，更新一遍U集中 其它点的距离。（选U集中的最短路径可以借助优先队列优化算法，用一个最小堆，每次弹出最短距离的顶点，结合used来判断是否作处理）

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n=grid.size();
        if(n==0)
            return -1;
        if(grid[0][0]==1)
            return -1;
        dist=vector<int>(n*n,10001);
        row=grid.size();
        col=grid[0].size();
        dijkstra(grid);
        return dist[n*n-1]==10001?-1:dist[n*n-1]+1;
    }
    
private:
    int row,col;
    vector<int> dist;
    bool canMove(int x,int y,vector<vector<int>> &grid){
        return x>=0 && x<row && y>=0 && y<col && grid[x][y]==0;
    };
    void dijkstra(vector<vector<int>> &grid){
        int n=grid.size();
        dist=vector<int>(n*n,10001);//代表从（0，0）到（row，col）的最短距离
        queue<int> qu;
        dist[0]=0;
        
        int d[8][2]={
            {-1,-1},
            {-1,0},
            {-1,1},
            {0,-1},
            {0,1},
            {1,-1},
            {1,0},
            {1,1}
        };
        qu.push(0);
        
        while(!qu.empty()){
            int vex=qu.front();
            qu.pop();
            
            int x=vex/row;
            int y=vex%row;
                
            for(int i=0;i<8;i++){
                int newX=x+d[i][0];
                int newY=y+d[i][1];
                if(canMove(newX,newY,grid)){
                    int point=newX*row+newY;
                    //update the path distance
                    if(dist[point]>dist[vex]+1)
                        {dist[point]=dist[vex]+1;
                         qu.push(point);
                        }                   
                }
            }
        }
    }
};