C++ में बढ़ते पानी में तैरना

मान लीजिए कि हमारे पास एक एन एक्स एन ग्रिड है, प्रत्येक वर्ग ग्रिड [i] [जे] उस बिंदु पर ऊंचाई का प्रतिनिधित्व करता है (i, j)। अब मान लीजिए बारिश शुरू हो गई है। समय t पर, हर जगह पानी की गहराई t होती है। हम एक वर्ग से दूसरे 4-प्रत्यक्ष रूप से आसन्न वर्ग में तैर सकते हैं जब दोनों वर्गों की ऊंचाई व्यक्तिगत रूप से अधिकतम t हो। हम शून्य समय में अनंत दूरी तैर सकते हैं।

हमें स्थिति (0, 0) से शुरू करना चाहिए। जब तक हम निचले दाएं वर्ग (N-1, N-1) तक नहीं पहुंच जाते, तब तक हमें कम से कम समय निकालना होगा

तो अगर इनपुट पसंद है

सही तरीका रंगीन है। तो उत्तर 16 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• डेटा को परिभाषित करें, इसमें समय, x और y जैसे तीन पैरामीटर लगेंगे।
• आकार की एक सरणी dir परिभाषित करें:4 x 2 :={ { 1, 0 }, { - 1, 0 }, { 0, 1 }, { 0, - 1 } }
• n :=ग्रिड की पंक्ति, m :=ग्रिड का स्तंभ
• प्राथमिकता कतार q परिभाषित करें
• एक 2D सरणी परिभाषित करें जिसका आकार n x m है, इसे 0 से भरें
• विज़िट किया[0, 0] :=1
• क्यू में डेटा (ग्रिड [0, 0], 0, 0) डालें
• जबकि (क्यू खाली नहीं है), करें −
  • नोड =q का शीर्ष तत्व और q से तत्व हटाएं
  • समय :=नोड का समय
  • x :=नोड का x, y :=y नोड का
  • यदि x, n-1 के समान है और y, m-1 के समान है, तो −
    • वापसी का समय
  • इनिशियलाइज़ i :=0 के लिए, जब i <4, अपडेट करें (i को 1 से बढ़ाएँ), −
    करें
    • nx:=dir[i, 0] + x, ny:=dir[i, 1] + y
    • अगर nx>=0 और nx =0 और ny
    • विज़िट किया[nx, y] :=1
    • क्यू में डेटा (अधिकतम ग्रिड [एनएक्स, एनवाई] और समय, एनएक्स, एनवाई) डालें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
struct Data{
   int time, x, y;
   Data(int a, int b, int y){
      time = a;
      x = b;
      this->y = y;
   }
};
struct Comparator{
   bool operator()(Data a, Data b){
      return !(a.time < b.time);
   }
};
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
   int swimInWater(vector<vector<int>>& grid) {
      int n = grid.size();
      int m = grid[0].size();
      priority_queue <Data, vector <Data>, Comparator> q;
      vector < vector <int> > visited(n, vector <int>(m, 0));
      visited[0][0] = 1;
      q.push(Data(grid[0][0], 0, 0));
      while(!q.empty()){
         Data node = q.top();
         q.pop();
         int time = node.time;
         int x = node.x;
         int y = node.y;
         if(x == n - 1 && y == m - 1)return time;
         for(int i = 0; i < 4; i++){
            int nx = dir[i][0] + x;
            int ny = dir[i][1] + y;
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]){
               visited[nx][y] = 1;
               q.push(Data(max(grid[nx][ny], time), nx, ny));
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},   {10,9,8,7,6}};
   cout << (ob.swimInWater(v));
}

इनपुट

{{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},{10,9,8,7,6}}

आउटपुट

16