মনে করুন, একটি N x N গ্রিড আছে, যেখানে grid[i][j] उस বিন্দুর (i,j) উচ্চতা নির্দেশ করে। এখন বৃষ্টি শুরু হয়েছে। সময় t-এ পানির গভীরতা সব জায়গায় t। আমরা একটি বর্গ থেকে অন্য ৪-দিকের যেকোনো সন্নিহিত বর্গে তখনই তাড়তে পারি যখন দুটি বর্গের উচ্চতা টি t-র চেয়ে কম বা সমান হয়। আমরা শূন্য সময়ে অসীম দুরি তাড়তে পারি।
আমরা (0, 0) থেকে শুরু করব। নিচের ডান কোণার বর্গ (N-1, N-1)-এ পৌঁছানোর জন্য ন্যূনতম সময় বের করতে হবে।
সমাধানের ধাপসমূহ
- Data স্ট্রাকচার সংজ্ঞায়িত করুন: time, x, y
- দিক নির্দেশক অ্যারে dir := {{1,0}, {-1,0}, {0,1}, {0,-1}}
- n := grid.size(), m := grid[0].size()
- প্রায়োরিটি কিউ q এবং n x m আকারের visited অ্যারে (০ দিয়ে ভরা) সংজ্ঞায়িত করুন
- visited[0][0] := 1, q-তে Data(grid[0][0], 0, 0) ঢুকান
- যখন q খালি নয়
- node := q.top(), q.pop()
- time := node.time, x := node.x, y := node.y
- যদি x == n-1 && y == m-1 হয়, time রিটার্ন করুন
- চারটি দিকের জন্য
- nx := x + dir[i][0], ny := y + dir[i][1]
- যদি বৈধ হয় এবং visited[nx][ny] == 0 হয়
- visited[nx][ny] := 1
- q-তে Data(max(grid[nx][ny], time), 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}}
আউটপুট
16
