सी++ में 01 मैट्रिक्स

मान लीजिए कि हमारे पास एक मैट्रिक्स है जिसमें 0 और 1 है, हमें प्रत्येक सेल के लिए निकटतम 0 की दूरी का पता लगाना है। यहाँ दो आसन्न कोशिकाओं के बीच की दूरी 1 है।

तो, अगर इनपुट पसंद है

तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आकार की एक सरणी dir परिभाषित करें:4 x 2 :={{1, 0}, {- 1, 0}, {0, - 1}, {0, 1}}

• n :=पंक्ति गणना, m :=स्तंभ गणना

• एक मैट्रिक्स रेट ऑफ़ ऑर्डर (n x m) को परिभाषित करें और इसे inf से भरें

• एक कतार को परिभाषित करें q

• इनिशियलाइज़ i :=0 के लिए, जब i

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • यदि मैट्रिक्स नहीं है [i, j] गैर-शून्य है, तो -

      • ret[i, j] :=0

      • q में {i, j} डालें

• lvl को इनिशियलाइज़ करने के लिए:=1, जब q खाली न हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), करें -

  • sz :=q का आकार

  • जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz को 1 से घटाएं, करें -

    • एक जोड़ी वक्र परिभाषित करें:=q का अग्र तत्व

    • q से तत्व हटाएं

    • इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -

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

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

      • यदि nx <0 या nx>=n या ny <0 या ny>=m या ret[nx, ny]

        • ret[nx, ny] :=lvl

      • q में {nx, ny} डालें

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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, ],]