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

總結(jié)：

1. constexpr是真正的常量，在編譯階段就已經(jīng)大膽計(jì)算出值。而const是一個(gè)只讀變量
2. queue<pair<int, int>> q;
   q.emplace(i, j);
   auto [i,j] = q.front(); // 注意，變量[i,j]同時(shí)獲得兩個(gè)值
3. 記?。?strong>超級(jí)源點(diǎn)的概念（用來BFS）

542. 01 矩陣

1. BFS
2. DP

狀態(tài)方程：

image.png

// 方法一：廣度優(yōu)先遍歷
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;
    }
};

// 方法二：動(dòng)態(tài)規(guī)劃
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. 腐爛的橘子

這道題不能用動(dòng)態(tài)規(guī)劃呀，只能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){
                    // 前面是標(biāo)準(zhǔn)的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;
    }
};