01 C++ 中的矩阵

c++server side programmingprogramming

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

因此，如果输入如下

0	0	0
0	1	0
1	1

则输出将是

0	0	0
0	1	0
1	2	1

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

定义一个大小为 4 x 2 := {{1, 0}, { - 1, 0}, {0, - 1}, {0, 1} 的数组 dir。
n := 行数，m := 列数
定义一个阶数为 (n x m) 的矩阵 ret，并用 inf 填充。
定义一个队列 q
初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
- 初始化 j := 0，当 j < m 时，更新(将 j 增加 1)，执行 −
  - 如果矩阵[i, j]不为零，则 −
    - ret[i, j] := 0
    - 将 {i, j} 插入 q
初始化 lvl := 1，当 q 不为空时，更新(将 lvl 增加 1)，执行 −
- sz := q 的大小
- 当 sz 非零时，在每次迭代中将 sz 减少 1，执行 −
  - 定义一对 curr := q 的前元素
  - 从 q 中删除元素
  - 初始化 k := 0，当 k < 4、更新(将 k 增加 1)，执行 −
    - nx := curr.first + dir[k, 0]
    - ny := curr.second + dir[k, 1]
    - 如果 nx < 0 或 nx >= n 或 ny < 0 或 ny >= m 或 ret[nx, ny] < lvl，则 −
      - ret[nx, ny] := lvl
    - 将 {nx, ny} 插入 q
return ret

Example

让我们看看下面的实现以便更好地理解 −

#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));
}