ধরুন আমাদের একটি 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"]
আউটপুট
2