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 সর্বনিম্ন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

ret :=inf
n :=গ্রিডের সারি আকার
m :=গ্রিডের col আকার
numberOfOnes :=0
n x m
আকারের একটি 2D অ্যারে ডিস্ট সংজ্ঞায়িত করুন
n x m
আকারের একটি 2D অ্যারে পৌঁছানোর সংজ্ঞা দিন
আরম্ভ করার জন্য i :=0, যখন i
- j শুরু করার জন্য :=0, যখন j করুন
  - যদি গ্রিড[i, j] 1 এর মত হয়, তাহলে −
    - (1 দ্বারা numberOfOnes বাড়ান)
    - একটি সারি 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, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −
        
        nx :=x + dir[k, 0]
        
        ny :=y + dir[k, 1]
        
        যদি nx এবং ny গ্রিড orgrid [nx,ny] 0 না হয়, তাহলে
        
        নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
        
        {nx, ny} ভিজিট করা
        -এ ঢোকান
        
        dist[nx, ny] :=dist[nx, ny] + lvl
        
        (1 দ্বারা নাগাল [nx, ny] বাড়ান)
        
        q
        -এ {nx, ny} ঢোকান
আরম্ভ করার জন্য i :=0, যখন i
- j শুরু করার জন্য :=0, যখন j করুন
  - যদি গ্রিড[i, j] 0 এর মত হয় এবং পৌঁছানো[i, j] নাম্বারOfOnes এর মত হয়, তাহলে −
    - ret :=ret এবং dist[i, j]
      ন্যূনতম
রিটার্ন (যদি ret একই হয় inf, তাহলে -1, অন্যথায় ret)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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