सी ++ में जितना संभव हो सके भूमि से दूर

मान लीजिए कि हमारे पास एक एन एक्स एन ग्रिड है जिसमें केवल 0 और 1 जैसे मान हैं, जहां 0 पानी का प्रतिनिधित्व करता है और 1 भूमि का प्रतिनिधित्व करता है, हमें एक जल सेल ढूंढना होगा जैसे कि निकटतम भूमि सेल से इसकी दूरी अधिकतम हो और दूरी वापस कर दें। यहां हम मैनहट्टन दूरी का उपयोग करेंगे - दो कोशिकाओं (x0, y0) और (x1, y1) के बीच की दूरी |x0 - x1| + |y0 - y1|। यदि ग्रिड में कोई भूमि या पानी मौजूद नहीं है, तो वापसी -1.

1	0	1
0	0	0
1	0	1

तब आउटपुट 2 होगा, क्योंकि सेल (1,1) दूरी 2 के साथ सभी भूमि से यथासंभव दूर है।

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

डीआईआर:=[(1, 0), (-1, 0), (1, -1), (1, 1), (-1, 1), (-1, -1), (0, 1) , (0, -1)]
dir2 :=[(1, 0), (-1, 0), (0, 1), (0, -1)]
मानचित्र को परिभाषित करें एम. एक कतार q को परिभाषित करें। n :=पंक्ति गणना और c :=स्तंभ गणना
मैं के लिए 0 से n - 1 की सीमा में
- j के लिए 0 से n - 1 की सीमा में
  - अगर ग्रिड [i, j] 1 है, तो q में एक युग्म (i, j) डालें और m[(i, j)] डालें:=(j ,i)
रिट :=-1
जबकि q खाली नहीं है
- sz :=q का आकार
- जबकि sz 0 नहीं है
  - अस्थायी:=q का पहला तत्व, q से पहला तत्व हटाएं
  - k के लिए 0 से 3 की सीमा में -
    - nx :=temp + dir2[k, 0]
      . का पहला मान
    - ny:=अस्थायी का दूसरा मान + dir2[k, 1]
    - यदि nx और ny ग्रिड की सीमा में नहीं हैं, या grid[nx, ny] 1 है, तो अगले पुनरावृत्ति पर जाएं।
    - एम [(एनएक्स, एनवाई)]:=एम [अस्थायी]
    - ret :=अधिकतम ((nx, ny) और m(temp) की दूरी) और ret
    - q में (nx, ny) डालें
    - ग्रिड सेट करें [एनएक्स, एनवाई]:=1
  - sz को 1 से घटाएं
वापसी रिट

उदाहरण(C++)

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

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {
   {1, 0}, {-1, 0}, {1, -1}, {1, 1},
   {-1, 1}, {-1, -1}, {0, 1}, {0, -1}
};
int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   int calcDist(int x1, int y1, int x2, int y2){
      return abs(x1 - x2) + abs(y1 - y2);
   }
   int maxDistance(vector<vector<int>>& grid) {
      map < pair <int, int>, pair <int, int> > m;
      queue < pair <int, int> > q;
      int n = grid.size();
      int c = n? grid[0].size() : 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < c; j++){
            if(grid[i][j] == 1){
               q.push({i, j});
               m[{i, j}] = {i, j};
            }
         }
      }
      int ret = -1;
      while(!q.empty()){
         int sz = q.size();
         while(sz--){
            pair <int, int> temp = q.front();
            q.pop();
            for(int k = 0; k < 4; k++){
               int nx = temp.first + dir2[k][0];
               int ny = temp.second + dir2[k][1];
               if(nx < 0 || ny < 0 || nx >= n || ny >= c || grid[nx][ny]) continue;
               m[{nx, ny}] = m[temp];
               ret = max(calcDist(nx, ny, m[temp].first,
               m[temp].second), ret);
               q.push({nx, ny});
               grid[nx][ny] = 1;
            }
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};
   Solution ob;
   cout << (ob.maxDistance(v1));
}

इनपुट

["alice,20,800,mtv","bob,50,1200,mtv"]