C++ এ রাইজিং ওয়াটারে সাঁতার কাটুন

ধরুন আমাদের একটি N x N গ্রিড আছে, প্রতিটি বর্গাকার গ্রিড[i][j] সেই বিন্দুতে (i,j) উচ্চতার প্রতিনিধিত্ব করে। এখন ধরুন বৃষ্টি শুরু হয়েছে। এ সময় টি, পানির গভীরতা সর্বত্র টি থাকে। আমরা একটি বর্গক্ষেত্র থেকে অন্য 4-দিকনির্দেশক সংলগ্ন বর্গক্ষেত্রে সাঁতার কাটতে পারি যখন পৃথকভাবে উভয় বর্গক্ষেত্রের উচ্চতা সর্বাধিক t হয়। আমরা শূন্য সময়ে অসীম দূরত্ব সাঁতার কাটতে পারি।

আমাদের অবস্থান থেকে শুরু করা উচিত (0, 0)। যতক্ষণ না আমরা নীচের ডান বর্গক্ষেত্রে পৌঁছতে পারি (N-1, N-1)

ততক্ষণ আমাদের সর্বনিম্ন সময় খুঁজে বের করতে হবে

তাই যদি ইনপুট মত হয়

৷ ৷

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।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

ডেটা সংজ্ঞায়িত করুন, এতে সময়, x এবং y এর মত তিনটি প্যারামিটার লাগবে।
আকারের একটি অ্যারে ডাইর সংজ্ঞায়িত করুন:4 x 2 :={ { 1, 0 }, { - 1, 0 }, { 0, 1 }, { 0, - 1 }
n :=গ্রিডের সারি, m :=গ্রিডের কলাম
অগ্রাধিকার সারি সংজ্ঞায়িত করুন q
n x m আকারের পরিদর্শন করা একটি 2D অ্যারে সংজ্ঞায়িত করুন, এটি 0 দিয়ে পূরণ করুন
ভিজিট করেছেন[0, 0] :=1
কিতে ডেটা (গ্রিড[0, 0], 0, 0) সন্নিবেশ করান
যখন (q খালি নয়), −
- নোড =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
  - কিতে ডেটা (সর্বাধিক গ্রিড[nx, ny] এবং সময়, nx, ny) সন্নিবেশ করান

রিটার্ন -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}}

C++ এ রাইজিং ওয়াটারে সাঁতার কাটুন

উদাহরণ

ইনপুট

আউটপুট