C ++中的01矩阵

假设我们有一个由0和1组成的矩阵，我们必须找到每个像元最接近0的距离。这里两个相邻像元之间的距离是1。

所以，如果输入像

那么输出将是

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为4 x 2的数组目录：= {{{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, ],]