-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
778.java
66 lines (60 loc) · 2.18 KB
/
778.java
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
__________________________________________________________________________________________________
sample 1 ms submission
class Solution {
public int swimInWater(int[][] grid) {
int n=grid.length,low=0,high=n*n-1,mid;
while(low<high){
mid = (low+high)/2;
if( possible(grid,mid) )
high = mid;
else
low = mid+1;
}
return low;
}
public static boolean possible(int grid[][],int time){
boolean visited[][] = new boolean[ grid.length ][ grid.length ];
return dfs( visited,grid,time,0,0 );
}
public static boolean dfs( boolean v[][],int g[][],int t,int i,int j){
if( i<0 || i>=g.length || j<0 || j>=g.length || v[i][j] )
return false;
v[i][j] = true;
if( g[i][j] > t )
return false;
if(i==g.length-1 && j==g.length-1)
return true;
return dfs(v,g,t,i+1,j) || dfs(v,g,t,i,j+1) || dfs(v,g,t,i-1,j) ||
dfs(v,g,t,i,j-1);
}
}
__________________________________________________________________________________________________
sample 36772 kb submission
class Solution {
public int swimInWater(int[][] grid) {
int N = grid.length;
Set<Integer> seen = new HashSet<Integer>();
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((k1, k2) ->
grid[k1 / N][k1 % N] - grid[k2 / N][k2 % N]);
pq.offer(0);
int ans = -1;
int[] dr = new int[]{1, -1, 0, 0};
int[] dc = new int[]{0, 0, 1, -1};
while (!pq.isEmpty()) {
int k = pq.poll();
int r = k / N, c = k % N;
ans = Math.max(ans, grid[r][c]);
if (r == N-1 && c == N-1) return ans;
for (int i = 0; i < 4; ++i) {
int cr = r + dr[i], cc = c + dc[i];
int ck = cr * N + cc;
if (0 <= cr && cr < N && 0 <= cc && cc < N && !seen.contains(ck)) {
pq.offer(ck);
seen.add(ck);
}
}
}
return ans;
}
}
__________________________________________________________________________________________________