01 Ma trận trong C ++

Giả sử chúng ta có một ma trận bao gồm 0 và 1, chúng ta phải tìm khoảng cách của 0 gần nhất cho mỗi ô. Ở đây khoảng cách giữa hai ô liền kề là 1.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định dir mảng có kích thước:4 x 2:={{1, 0}, {- 1, 0}, {0, - 1}, {0, 1}}

• n:=số hàng, m:=số cột

• Xác định một thứ tự của ma trận (n x m) và điền vào điều này với inf

• Xác định một hàng đợi q

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • nếu không ma trận [i, j] khác 0 thì -

      • ret [i, j]:=0

      • chèn {i, j} vào q

• để khởi tạo lvl:=1, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), thực hiện -

  • sz:=kích thước của q

  • trong khi sz khác 0, giảm sz đi 1 trong mỗi lần lặp, thực hiện -

    • Xác định một cặp curr:=phần tử phía trước của q

    • xóa phần tử khỏi q

    • để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -

      • nx:=curr.first + dir [k, 0]

      • ny:=curr.second + dir [k, 1]

      • nếu nx <0 hoặc nx> =n hoặc ny <0 hoặc ny> =m hoặc ret [nx, ny]

        • ret [nx, ny]:=lvl

      • chèn {nx, ny} vào q

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

{{0,0,0},{0,1,0},{1,1,1}}

Đầu ra

[[0, 0, 0, ],[0, 1, 0, ],[1, 2, 1, ],]