C++ এ যতটা সম্ভব জমি থেকে যতদূর সম্ভব

ধরুন আমাদের একটি N x N গ্রিড আছে যেখানে শুধুমাত্র 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 সহ সমস্ত জমি থেকে যতদূর সম্ভব।

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

dir :=[(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)]
একটি মানচিত্র সংজ্ঞায়িত করুন m. একটি সারি q সংজ্ঞায়িত করুন। n :=সারি গণনা এবং c :=কলাম গণনা
0 থেকে n – 1
রেঞ্জের i জন্য
- j-এর জন্য 0 থেকে n – 1
  পরিসরে
  - যদি গ্রিড[i, j] 1 হয়, তাহলে q এ একটি জোড়া (i, j) ঢোকান এবং m[(i, j)] :=(j,i)
ret :=-1
যখন q খালি থাকে না
- sz :=q এর আকার
- যখন sz 0
  নয়
  - temp :=q এর প্রথম উপাদান, q থেকে প্রথম উপাদান মুছুন
  - k এর জন্য 0 থেকে 3 −
    পরিসরে
    - nx :=temp + dir2[k, 0]
      এর প্রথম মান
    - ny :=temp + dir2[k, 1]
      এর দ্বিতীয় মান
    - যদি nx এবং ny গ্রিডের পরিসরে না হয়, অথবা গ্রিড[nx, ny] 1 হয়, তাহলে পরবর্তী পুনরাবৃত্তিতে চলে যান।
    - m[(nx, ny)] :=m[temp]
    - ret :=সর্বোচ্চ (এর দূরত্ব (nx, ny) এবং m(temp)) এবং ret
    - q
      -এ (nx,ny) সন্নিবেশ করান
    - গ্রিড সেট করুন [nx, ny] :=1
  - 1 দ্বারা sz হ্রাস করুন
রিটার্ন রিটার্ন

উদাহরণ(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"]