01 矩阵在 C++ 中


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

所以,如果输入如下:

000
010
111

那么输出将是

000
010
121

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

  • 定义一个大小为 4 x 2 的数组 dir := {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}

  • n := 行数,m := 列数

  • 定义一个 (n x m) 阶矩阵 ret 并将其填充为无穷大 (inf)

  • 定义一个队列 q

  • 初始化 i := 0,当 i < n 时,更新 (i 加 1),执行:

    • 初始化 j := 0,当 j < m 时,更新 (j 加 1),执行:

      • 如果 matrix[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

  • 返回 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, ],]

更新于:2020年11月17日

179 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告