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

ধরুন আমাদের একটি N x N গ্রিড আছে যেখানে শুধুমাত্র 0 এবং 1 এর মত মান রয়েছে, যেখানে 0 জলের প্রতিনিধিত্ব করে এবং 1 ভূমিকে প্রতিনিধিত্ব করে, আমাদের এমন একটি জল কোষ খুঁজে বের করতে হবে যাতে নিকটতম ভূমি কোষের দূরত্ব সর্বাধিক হয় এবং দূরত্ব ফেরত দেয়। এখানে আমরা ম্যানহাটান দূরত্ব ব্যবহার করব − দুটি কোষ (x0, y0) এবং (x1, y1) এর মধ্যে দূরত্ব হল |x0 - x1| + |y0 - y1|। যদি গ্রিডে কোন জমি বা পানি না থাকে, তাহলে -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"]

আউটপুট

2