542. 01 矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入: 输出:
0 0 0 0 0 0
0 1 0 0 1 0
0 0 0 0 0 0
示例 2:
输入: 输出:
0 0 0 0 0 0
0 1 0 0 1 0
1 1 1 1 2 1
方法一：动态规划
思路：
从一个位置到0所在位置，可以有四种走法，往左往上；往左往下；往右往上；往右往下。实际dp中，是反过来计算的，也就是要注意循环的起始和终止，不能搞反了。举个例子，往左往上时，对应的dp是往右往下，那么dp的初始位置就是在[0,0]了，循环的时候行和列都是从0开始的。[i,j]位置往左往上时，dp数组的值是dp[i][j]自己的值；往左走一步，到dp[i][j-1]，也就是dp[i][j-1]+1；往上走一步，到dp[i-1][j]，也就是dp[i-1][j]+1；三者的最小值。
最后的dp数组是四种走法全都走过后的最小值。
可以将dp数组初始化为最大，但是进行算数运算时，可能会超过最大范围，因此初始化为INT_MAX/2。
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0)
return {};
int row = matrix.size(), col = matrix[0].size();
vector<vector<int>> dp(row,vector<int>(col,INT_MAX/2));
for (int i = 0; i<row; ++i)
{
for(int j=0;j<col;++j)
{
if(matrix[i][j]==0) //原数组是0的，dp数组也是0
dp[i][j]=0;
}
}
//往左往上移动，那么实际dp时应该从[0,0]位置往右往下
for(int i=0;i<row;++i)
{
for(int j=0;j<col;++j)
{
if(i-1>=0) //往上走一步到dp[i-1][j]
dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
if(j-1>=0) //往左走一步到dp[i][j-1]
dp[i][j]=min(dp[i][j],dp[i][j-1]+1);//INT_MAX+1会超过INT_MAX，故上面取一半
}
}
//往左往下，那么实际dp时应该从[row-1,0]往右往上
for(int i=row-1;i>=0;--i)
{
for(int j=0;j<col;++j)
{
if(i+1<row) //往下走一步到dp[i+1][j]
dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
if(j-1>=0) //往左走一步到dp[i][j-1]
dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
}
}
//往右往上，那么实际dp时应该从[0,col-1]往左往下
for(int i=0;i<row;++i)
{
for(int j=col-1;j>=0;--j)
{
if(i-1>=0) //往上走一步到dp[i-1][j]
dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
if(j+1<col) //往下走一步到dp[i][j+1]
dp[i][j]=min(dp[i][j],dp[i][j+1]+1);
}
}
//往右往下，那么实际dp时应该从[row-1,col-1]往左往上
for(int i=row-1;i>=0;--i)
{
for(int j=col-1;j>=0;--j)
{
if(i+1<row) //往上走一步到dp[i+1][j]
dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
if(j+1<col) //往下走一步到dp[i][j+1]
dp[i][j]=min(dp[i][j],dp[i][j+1]+1);
}
}
return dp;
}
};
方法二：广度优先搜索(BFS)
思路：
广度优先搜索大水漫灌形式的一层层遍历，首先将位置为0的位置全部入队，并建立辅助向量标记元素是否访问过，当出队时，遍历其四个方向的位置，如果有没有访问过的，那么入队，并标记为已访问过，该位置的值为出队位置的值加1。
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0)
return {};
int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; // 代表四个方向 4 2不写会报错
int row=matrix.size(),col=matrix[0].size();
vector<vector<int>> res(row,vector<int>(col,0)); //存放某一位置的值
vector<vector<bool>> visited(row,vector<bool>(col,false)); //标记是否访问过
queue<pair<int,int>> q; //队列，元素为 横纵坐标[i,j]
for(int i=0; i<row; ++i) //位置为0的入队
{
for(int j=0; j<col; ++j)
{
if(matrix[i][j]==0)
{
visited[i][j]=true;
q.push({i,j});
}
}
}
while(!q.empty())
{
auto tmp=q.front();
q.pop();
for(int i=0;i<4;++i) //遍历位置tmp的上下左右四个方向
{
int nexti=tmp.first+direction[i][0];//tmp[0] tmp[1]是不合法的
int nextj=tmp.second+direction[i][1];
if(nexti>=0&&nexti<row&&nextj>=0&&nextj<col&&!visited[nexti][nextj]) //下标没越界，且没有访问过该位置
{
visited[nexti][nextj]=true;
res[nexti][nextj]=res[tmp.first][tmp.second]+1;
q.push({nexti,nextj});
}
}
}
return res;
}
};
小知识：
- vector批量初始化
vector<vector<int>> res(row,vector<int>(col,0));
vector<vector<bool>> visited(row,vector<bool>(col,false));
- 定义数组指定行列数
int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
- pair类型元素获取
pair<int,int> p;
p.first;
p.second;
- 队列push
queue<pair<int,int>> q;
q.push({nexti,nextj}); //队列存储的是一个元素，而该元素的组成可以是多个
- 用二维数组表示方向
int nexti=tmp.first+direction[i][0];
int nextj=tmp.second+direction[i][1];
网友评论