-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
38 lines (37 loc) · 1.11 KB
/
Solution.cs
File metadata and controls
38 lines (37 loc) · 1.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution
{
public int SwimInWater(int[][] grid)
{
int n = grid.Length;
int[][] need = new int[n][];
for (int i = 0; i < n; i++)
{
need[i] = new int[n];
Array.Fill(need[i], int.MaxValue);
}
PriorityQueue<(int r, int c, int v), int> pq = new();
pq.Enqueue((0, 0, grid[0][0]), grid[0][0]);
need[0][0] = grid[0][0];
int[] dirs = [1, 0, -1, 0, 1];
while (pq.Count > 0)
{
var (r, c, v) = pq.Dequeue();
for (int i = 0; i < 4; i++)
{
int nR = r + dirs[i];
int nC = c + dirs[i + 1];
if (IsValid(nR, nC, n))
{
int nV = Math.Max(v, grid[nR][nC]);
if (nV < need[nR][nC])
{
need[nR][nC] = nV;
pq.Enqueue((nR, nC, nV), nV);
}
}
}
}
return need[n - 1][n - 1];
}
bool IsValid(int r, int c, int n) => r >= 0 && r < n && c >= 0 && c < n;
}