752. Open the Lock 815. Bus Routes 1091. Shortest Path in Binary Matrix 542. 01 Matrix

标准的采用BFS的解法，初始从“００００”开始，每次可以+1或者-1，如果没有再终止字符串中，且没有被访问过。可以存入到队列中，反之不行。 所以需要一个map来确定是否在终止字符串中，需要一个visited来确定是否被访问过，一个队列。

class Solution {
public:
    int openLock(vector& deadends, string target) {
    
        unordered_set m(deadends.begin(), deadends.end());
        unordered_set visited;
        if(m.find("0000") != m.end()) return -1;
        //初始0000-target
        queue q;
        int res=0;
        q.push("0000");
        visited.insert("0000");
        while(!q.empty()){
            int siz = q.size();
            for(int i=0; i 
815. Bus Routes 
题解 
采用一个map存放每个站点在那几个班次，一个map用来看那个站点被访问过，一个map用来看那个班次的班车被访问过，一个队列，里面存放的时当前访问的站点和坐过的班车。采用BFS的方法进行遍历。首先从source开始，然后看source在那几个班次中，然后将班次没有走过的站点加入进去。依次进行。
 
 
代码 
class Solution {
public:
    int numBusesToDestination(vector>& routes, int source, int target) {
        int n = routes.size();
        unordered_map> m;
        for(int i=0; i visStation;
        unordered_map visBus;
        queue> q;
        q.push({source,0});
        while(!q.empty()){
            int curSta = q.front().first;
            int curVal = q.front().second;
            if(curSta==target) return curVal;
            q.pop();
            visStation[curSta]=true;//该站点已经被访问过
            for(auto busNo:m[curSta]){
                //看又那几班车次包含次站点
                if(visBus[busNo]) continue;
                for(auto nextSta:routes[busNo]){
                    if(visStation.find(nextSta)==visStation.end()){
                        q.push({nextSta, curVal+1});
                    }
                }
                visBus[busNo] = true;
                
            }
                
        }
        return -1;
    }
};
 
1091. Shortest Path in Binary Matrix 
题解 
采用 标准 的BFS套路进行求解。需要一个visited来判断那个位置是否被访问过，需要一个方向向量来进行当前节点的八个方向的遍历。如果没有被访问过且安全，那么入队。
 
代码 
class Solution {
public:
    bool safe(int x, int y, int n ){
        if(x>=0 && x <=n && y>=0 && y<=n)
            return true;
        return false;
    }
    int shortestPathBinaryMatrix(vector>& grid) {
         
        int n = grid.size()-1;
        vector> visited(n+1, vector (n+1, false));
        queue> q;
        if(grid[0][0]==0){
            q.push({0,0});//起始点{0，0} 目标点{grid.size()-1, grid.size()-1};
            visited[0][0]=true;
        }
       
        int res =0;
        vector> dir = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,-1},{-1,1}};
        
        while(!q.empty()){
            int siz = q.size();
            res++;
            for(int i=0; i temp = q.front();
                q.pop();
                // cout< 
542. 01 Matrix 
题解 
可以将等于0的下标入队，非0的位置的值设置为无限大INT_MAX, 然后寻找遍历其周围的节点的值，如果周围节点的值比当前节点的值大，下标入队{为什么入队? 当前节点的值大的情况只有二种1、初始矩阵值为1的下标，2、被改过的值，此时需要变成最小的距离，要当前节点值+1，入对：是为了查找其周围节点中，初始矩阵mat值为1的节点，然后改变其变换的距离}，然后调整为当前节点的值+1， 反之如果小，不需要改变这个周围节点的值。，
 
代码 
class Solution {
public:

   
    vector> updateMatrix(vector>& mat) {
        int m=mat.size(), n=mat[0].size();
        vector> dirs = {{0,1},{0,-1},{-1,0},{-1,-1}};
        queue>q;
        //将等于0的坐标入队
        for(int i=0; ix+1 那么时temp位置的值调整为最短
                if(x<0 || x>=n || y<0 || y>=n || mat[x][y] <= mat[temp.first][temp.second] + 1) continue;
                // Adds one distance to the adjacent cell.
                mat[x][y] = mat[temp.first][temp.second] + 1;
                q.push({x, y});
                
            }
        }
        return mat;
        
    }
};