完成日期：7月21日，7月22日
总结：
- constexpr是真正的常量，在编译阶段就已经大胆计算出值。而const是一个只读变量
- queue<pair<int, int>> q;
q.emplace(i, j);
auto [i,j] = q.front(); // 注意，变量[i,j]同时获得两个值 - 记住：超级源点的概念（用来BFS）
542. 01 矩阵
- BFS
- 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;
}
};
