C ++中的01矩阵
假设我们有一个由0和1组成的矩阵，我们必须找到每个像元最接近0的距离。这里两个相邻像元之间的距离是1。
所以，如果输入像
那么输出将是
为了解决这个问题，我们将遵循以下步骤-
定义大小为4x2的数组目录：={{{1，0}，{-1，0}，{0，-1}，{0，1}}
n：=行数，m：=列数
定义一个阶数为(nxm)的矩阵ret，并用inf填充
定义一个队列q
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
如果不是matrix[i，j]为非零，则-
ret[i，j]：=0
将{i，j}插入q
对于初始化j：=0，当j<m时，更新（将j增加1），执行-
对于初始化lvl：=1，当非q为空时，更新（将lvl增加1），执行-
定义一对curr：=q的前元素
从q删除元素
对于初始化k：=0，当k<4时，更新（将k增加1），执行-
ret[nx，ny]：=lvl
nx：=curr.first+dir[k，0]
ny：=curr.second+dir[k，1]
如果nx<0或nx>=n或ny<0或ny>=m或ret[nx，ny]<lvl，则-
将{nx，ny}插入q
sz：=q的大小
当sz为非零值时，请在每次迭代中将sz减1，然后执行-
返回ret
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector < vector <int> > ret(n, vector <int>(m, INT_MAX));
queue < pair <int, int> > q;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!matrix[i][j]){
ret[i][j] = 0;
q.push({i, j});
}
}
}
for(int lvl = 1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
pair <int, int> curr = q.front();
q.pop();
for(int k = 0; k < 4; k++){
int nx = curr.first + dir[k][0];
int ny = curr.second + dir[k][1];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || ret[nx][ny] < lvl) continue;
ret[nx][ny] = lvl;
q.push({nx, ny});
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0,0},{0,1,0},{1,1,1}};
print_vector(ob.updateMatrix(v));
}输入值
{{0,0,0},{0,1,0},{1,1,1}}输出结果
[[0, 0, 0, ],[0, 1, 0, ],[1, 2, 1, ],]