C++ . में सभी भवनों से सबसे कम दूरी

मान लीजिए हम एक खाली जमीन पर एक घर बनाना चाहते हैं जो कम से कम दूरी में सभी इमारतों तक पहुंच जाए। हम केवल चार दिशाओं को ऊपर, नीचे, बाएँ और दाएँ घुमा सकते हैं। हमारे पास 0, 1 या 2 मानों का 2D ग्रिड है, जहां -

0 एक खाली भूमि का प्रतिनिधित्व करता है जिसे हम स्वतंत्र रूप से पारित कर सकते हैं।
1 एक ऐसी इमारत का प्रतिनिधित्व करता है जिससे हम नहीं गुजर सकते।
2 एक बाधा का प्रतिनिधित्व करता है जिसे हम पार नहीं कर सकते।

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

1	2	1
0	0	0
0	1	0

तो आउटपुट 7 होगा क्योंकि दिए गए तीन भवन (0,0), (0,4), (2,2) पर मौजूद हैं, और एक बाधा (0,2) पर है, इसलिए बिंदु (1,2) है घर बनाने के लिए एक आदर्श खाली भूमि, क्योंकि कुल यात्रा दूरी 3+3+1=7 न्यूनतम है।

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

रिट :=inf
n :=ग्रिड की पंक्ति का आकार
मी :=ग्रिड का कॉलम आकार
नंबरऑफवन्स :=0
n x m आकार के एक 2D सरणी को परिभाषित करें
n x m आकार की एक 2D सरणी पहुंच परिभाषित करें
इनिशियलाइज़ i:=0 के लिए, जब i
- इनिशियलाइज़ j :=0 के लिए, जब j
  - अगर ग्रिड [i, j] 1 के समान है, तो -
    - (संख्या 1 से बढ़ाएं)
    - एक कतार को परिभाषित करें q
    - q में {i, j} डालें
    - देखे गए एक सेट को परिभाषित करें
    - lvl को इनिशियलाइज़ करने के लिए:=1, जब q खाली न हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), करें -
      - sz :=q का आकार
      - जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz घटाएं, −
        . करें
        
        curr :=q का पहला तत्व
        
        q से तत्व हटाएं
        
        x :=curr.first
        
        y :=curr.second
        
        इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -
        
        एनएक्स:=एक्स + डीआईआर [के, 0]
        
        ny :=y + dir[k, 1]
        
        अगर nx और ny ग्रिड ऑर्ग्रिड की सीमा में हैं [nx, ny] 0 नहीं है, तो
        
        निम्नलिखित भाग पर ध्यान न दें, अगले भाग पर जाएं
        
        विज़िट किए गए में {nx, ny} डालें
        
        जिला [एनएक्स, एनवाई]:=जिला [एनएक्स, एनवाई] + एलवीएल
        
        (पहुंच में वृद्धि[nx, ny] 1 से)
        
        q में {nx, ny} डालें
इनिशियलाइज़ i:=0 के लिए, जब i
- इनिशियलाइज़ j :=0 के लिए, जब j
  - अगर ग्रिड [i, j] 0 के समान है और पहुंच [i, j] नंबरऑफऑन के समान है, तो -
    - रिट:=न्यूनतम सेवानिवृत्त और जिला[i, j]
वापसी (यदि रिट inf के समान है, तो -1, अन्यथा रिट)

उदाहरण

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

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
   int shortestDistance(vector<vector<int>>& grid) {
      int ret = INT_MAX;
      int n = grid.size();
      int m = grid[0].size();
      int numberOfOnes = 0;
      vector < vector <int> > dist(n, vector <int>(m));
      vector < vector <int> > reach(n, vector <int>(m));
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 1){
               numberOfOnes++;
               queue < pair <int, int> > q;
               q.push({i, j});
               set < pair <int, int> > visited;
               for(int lvl = 1; !q.empty(); lvl++){
                  int sz = q.size();
                  while(sz--){
                     pair <int, int> curr = q.front();
                     q.pop();
                     int x = curr.first;
                     int y = curr.second;
                     for(int k = 0; k < 4; k++){
                        int nx = x + dir[k][0];
                        int ny = y + dir[k][1];
                        if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;
                        visited.insert({nx, ny});
                        dist[nx][ny] += lvl;
                        reach[nx][ny]++;
                        q.push({nx, ny});
                     }
                  }
               }
            }
         }
      }
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){
               ret = min(ret, dist[i][j]);
            }
         }
      }
      return ret == INT_MAX ? -1 : ret;
   }
};

इनपुट

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