मान लीजिए हमारे पास एक N x N ग्रिड है, प्रत्येक वर्ग grid[i][j] उस बिंदु (i,j) पर ऊंचाई (elevation) को दर्शाता है। अब मान लीजिए बारिश शुरू हो गई है। समय t पर, हर जगह पानी की गहराई t है। हम एक वर्ग से दूसरे 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 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- Data परिभाषित करें, यह तीन पैरामीटर लेगा जैसे time, x और y।
- आकार 4 x 2 का एक ऐरे dir परिभाषित करें := { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }
- n := grid की पंक्तियां, m := grid के स्तंभ
- प्रायोरिटी क्यू q परिभाषित करें
- आकार n x m का एक 2D ऐरे visited परिभाषित करें, इसे 0 से भरें
- visited[0, 0] := 1
- Data(grid[0, 0], 0, 0) को q में डालें
- जब (q खाली नहीं है), करें -
- node = q का शीर्ष तत्व और q से तत्व हटाएं
- time := node का time
- x := node का x, y := node का y
- यदि x, n - 1 के समान है और y, m - 1 के समान है, तो -
- time वापस करें
- i := 0 से प्रारंभ करें, जब i < 4, i बढ़ाते हुए, करें -
- nx := dir[i, 0] + x, ny := dir[i, 1] + y
- यदि nx >= 0 और nx < n और ny >= 0 और ny < m और visited[nx, ny] नहीं है तो -
- visited[nx, y] := 1
- Data(grid[nx, ny] और time का अधिकतम, nx, ny) को q में डालें
- -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
