मान लीजिए हमारे पास एक 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 := कॉलम गणना iको 0 सेn - 1तक लूप करेंjको 0 सेn - 1तक लूप करें- यदि
grid[i, j] = 1, तो जोड़ी(i, j)कोqमें डालें औरm[(i, j)] := (j, i)रखें
- यदि
ret := -1- जब तक
qखाली नहीं हैsz := q का आकार- जब तक
sz0 नहीं हैtemp := q का पहला तत्व,qसे पहला तत्व हटाएंkको 0 से 3 तक लूप करेंnx := temp का पहला मान + dir2[k, 0]ny := temp का दूसरा मान + dir2[k, 1]- यदि
nxऔरnyग्रिड की सीमा में नहीं हैं, याgrid[nx, ny] = 1, तो अगले पुनरावृत्ति पर जाएं। m[(nx, ny)] := m[temp]ret := (nx, ny) और m(temp) की दूरी और ret का अधिकतम(nx,ny)कोqमें डालेंgrid[nx, ny] := 1सेट करें
szको 1 से घटाएं
retलौटाएं
उदाहरण (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)); }इनपुट
[[1,0,1],[0,0,0],[1,0,1]]
आउटपुट
2