完成日期：7月21日，7月22日

总结：

1. constexpr是真正的常量，在编译阶段就已经大胆计算出值。而const是一个只读变量
2. queue<pair<int, int>> q;
   q.emplace(i, j);
   auto [i,j] = q.front(); // 注意，变量[i,j]同时获得两个值
3. 记住：超级源点的概念（用来BFS）

542. 01 矩阵

1. BFS
2. DP

状态方程：

image.png

// 方法一：广度优先遍历
class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> seen(m, vector<int>(n));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for ( int j = 0; j < n; ++j) {
                if (mat[i][j] == 0) {
                    q.emplace(i, j);
                    seen[i][j] = 1;
                }
            }
        }
        while(!q.empty()) {
            auto [i,j] = q.front();  // 注意，变量[i,j]
            q.pop();
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >=0 && ni < m && nj >=0 && nj < n && !seen[ni][nj]) { 
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }
        return dist;
    }
};

// 方法二：动态规划
class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX / 2));  //为什么要/2?
        for(int i = 0; i<m; ++i){
            for(int j = 0; j<n; ++j){
                if(mat[i][j] == 0){
                    dist[i][j] = 0;
                }
            }
        }
        for(int i = 0; i<m; i++){
            for(int j=0; j<n; ++j){
                if(i-1>=0){
                    dist[i][j] = min(dist[i][j], dist[i-1][j]+1);
                }
                if(j-1>=0){
                    dist[i][j] = min(dist[i][j], dist[i][j-1]+1);
                }
            }
        }
        for(int i =m-1; i>=0; --i){
            for(int j =n-1; j>=0; --j){
                if(i+1<m){
                    dist[i][j] = min(dist[i][j], dist[i+1][j]+1);
                }
                if(j+1<n){
                    dist[i][j] = min(dist[i][j], dist[i][j+1]+1);
                }
            }
        }
        return dist;


    }
};

994. 腐烂的橘子

这道题不能用动态规划呀，只能BFS

厉害了，自己参考上一题模板写的，加油

class Solution {

private:
    static constexpr int dirs[4][2] = {{-1,0}, {1,0}, {0,1}, {0,-1}};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> time(m, vector<int>(n));
        vector<vector<int>> seen(m, vector<int>(n));
        queue<pair<int, int>> q;
        int res = 0;
        int oneNum=0;

        for(int i=0; i<m; i++){
            for(int j=0; j<n; ++j){
                if(grid[i][j]==2){
                    q.emplace(i, j);
                    seen[i][j]=1;
                }else if(grid[i][j]==1){
                    oneNum++;
                }
            }
        }

        if(!oneNum) return 0;

        while(!q.empty()){
            auto [i,j] = q.front();
            q.pop();
            for(int d=0; d<4; ++d){
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if(ni>=0 && nj>=0 && ni<m && nj<n && seen[ni][nj]!=1){
                    // 前面是标准的BFS模板，从这里写具体判断
                    if(grid[ni][nj]==1){
                        seen[ni][nj]=1;
                        time[ni][nj] = time[i][j]+1;
                        q.emplace(ni,nj);
                        res = time[ni][nj];
                        oneNum--;
                    }
                }
            }
        }
        if(oneNum) return -1;
        return res;
    }
};