C++-এ ভূমি থেকে যেনে সম্ভব দূরতম জলকোষ्ठ

একটি N x N গ্রিড দেওয়া আছে যেটি শুধু ০ আর ১ ধারণ করে, যেখানে ০ জল বোঝায় আর ১ ভূমি। এমন একটি জল কোষ্ঠ খুঁজে বের করতে হবে যাতে তার নিকটতম ভূমি কোষ্ঠ হতে দূরত্ব সর্বোচ্চ হয়। এখানে ম্যানহ্যাটান দূরত্ব ব্যবহার করা হয়: দুটি কোষ্ঠ (x0, y0) আর (x1, y1)-র দূরত্ব = |x0 - x1| + |y0 - y1|। যদি গ্রিডে কোনো ভূমি বা জল না থাকে, -১ ফেরত দিন।

আউটপুট হবে ২, কারণ কোষ্ঠ (1,1) সব ভূমি থেকে দূরত্ব ২-এ আছে।

সমাধানের ধাপগুলো:

• 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, q-তে (i,j) ঢোকান, m[(i,j)] := (i,j)।
• ret := -1
• q খালি না হওয়া পর্যন্ত:
  • sz := q.size()
  • sz != 0 रहने পর্যন্ত:
    • temp := q.front(), q.pop()
    • k = 0 থেকে 3 পর্যন্ত:
      • nx := temp.first + dir2[k][0]
      • ny := temp.second + dir2[k][1]
      • যদি nx, ny গ্রিডের বাইরে হয় অথবা grid[nx][ny] == 1, পরবর্তী ইটারেশনে যান।
      • m[(nx,ny)] := m[temp]
      • ret := max( (nx,ny) আর m[temp] এর দূরত্ব, ret )
      • q.push({nx,ny})
      • grid[nx][ny] := 1
    • sz--
• 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)); }

ইনপুট

["alice,20,800,mtv","bob,50,1200,mtv"]

আউটপুট

2