ภาพรวมปัญหา
สมมติว่ามีตาราง N x N แต่ละเซลล์ grid[i][j] แสดงความสูงที่จุด (i,j) เริ่มฝนตก ที่เวลา t ระดับน้ำทุกที่ = t เราสามารถว่ายน้ำจากเซลล์หนึ่งไปอีกเซลล์หนึ่ง (4 ทิศทาง) ได้ก็ต่อเมื่อความสูงของทั้งสองเซลล์ ≤ t เราสามารถว่ายน้ำได้ไกลแค่ไหนก็ได้ในเวลา 0 เริ่มจาก (0, 0) หาเวลาน้อยที่สุดที่ไปถึง (N-1, N-1) ได้
ตัวอย่าง
Grid 5x5 ที่แสดงในตาราง → Output: 16
แนวทางแก้ปัญหา (Dijkstra / Priority Queue)
- ใช้ Priority Queue (Min-Heap) เก็บสถานะ (เวลา, x, y)
- เริ่มจาก (grid[0][0], 0, 0)
- Pop สถานะที่เวลาน้อยสุด ถ้าถึง (n-1, m-1) คืนค่าเวลา
- ขยายไป 4 ทิศทาง: เวลาใหม่ = max(เวลาปัจจุบัน, grid[nx][ny])
- ใช้ visited array ป้องกันการเยี่ยมชมซ้ำ
ตัวอย่างโปรแกรม
#include <bits/stdc++.h>
using namespace std;
struct Data {
int time, x, y;
Data(int a, int b, int c) { time = a; x = b; y = c; }
};
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, x = node.x, 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, ny = dir[i][1] + y;
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
visited[nx][ny] = 1;
q.push(Data(max(grid[nx][ny], time), nx, ny));
}
}
}
return -1;
}
};
int 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));
}
Input
{{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}}
Output
16
