leetcode778

 1  public static int swimInWater(int[][] grid) {
 2 
 3         int[][] forward = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
 4 
 5 
 6         int n = grid.length;
 7         int len = n*n-1;
 8         for (int i = 0; i <= len; i++) {
 9             //如果有满足K的就返回
10             int k = i;
11             PriorityQueue<Tmo> pq = new PriorityQueue<>();
12             pq.offer(new Tmo(0,0,grid[0][0]));
13 
14             int[][] exist = new int[n][n];
15             exist[0][0] = 1;
16 
17             while (!pq.isEmpty()){
18                 Tmo poll = pq.poll();
19                 int x = poll.x;
20                 int y = poll.y;
21                 //朝着四个方向出发  选择短路径 如果结果是N,N则返回
22                 for (int j = 0; j < forward.length && poll.value <= k; j++) {
23                     //控制方向
24                     int[] forw = forward[j];
25                     int tx = x+forw[0];
26                     int ty = y+forw[1];
27                     if (tx <0 || tx >= n || ty <0 || ty >= n || exist[tx][ty] == 1 || grid[tx][ty] > k  ){
28                         continue;
29                     }
30                     if (tx == n-1 && ty ==  n-1 ){
31                         return k;
32                     }
33                     exist[tx][ty] = 1;
34                     pq.offer(new Tmo(tx,ty,grid[tx][ty]));
35 
36                 }
37 
38             }
39 
40 
41 
42         }
43 
44 
45 
46         return -1;
47     }
48 
49 
50     static class Tmo implements Comparable<Tmo> {
51         public int x;
52 
53         public int y;
54 
55         public int value;
56 
57         public Tmo(int x, int y, int value) {
58             this.x = x;
59             this.y = y;
60             this.value = value;
61         }
62 
63 
64         @Override
65         public int compareTo(Tmo o) {
66             return o.value -this.value;
67         }
68     }

 1     public static int swimInWater(int[][] grid) {
 2 
 3         int[][] forward = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
 4 
 5 
 6         int n = grid.length;
 7         int start = 0;
 8         int end = n*n-1;
 9         while (start <= end){
10             //如果有满足K的就返回
11             int middle = (end + start)/2;
12 
13             PriorityQueue<Tmo> pq = new PriorityQueue<>();
14             pq.offer(new Tmo(0,0,grid[0][0]));
15 
16             int[][] exist = new int[n][n];
17             exist[0][0] = 1;
18             boolean search = false;
19             while (!pq.isEmpty()){
20                 Tmo poll = pq.poll();
21                 int x = poll.x;
22                 int y = poll.y;
23                 //朝着四个方向出发  选择短路径 如果结果是N,N则返回
24                 for (int j = 0; j < forward.length && poll.value <= middle; j++) {
25                     //控制方向
26                     int[] forw = forward[j];
27                     int tx = x+forw[0];
28                     int ty = y+forw[1];
29                     if (tx <0 || tx >= n || ty <0 || ty >= n || exist[tx][ty] == 1 || grid[tx][ty] > middle  ){
30                         continue;
31                     }
32                     if (tx == n-1 && ty ==  n-1 ){
33                         search = true;
34                         break;
35                     }
36                     exist[tx][ty] = 1;
37                     pq.offer(new Tmo(tx,ty,grid[tx][ty]));
38 
39                 }
40 
41             }
42             if (search){
43                 //当前点符合 就寻找小的是不是有符合的
44                 end = middle-1;
45             }else {
46                 start = middle +1;
47             }
48         }
49 
50 
51 
52         return start;
53     }
54 
55 
56     static class Tmo implements Comparable<Tmo> {
57         public int x;
58 
59         public int y;
60 
61         public int value;
62 
63         public Tmo(int x, int y, int value) {
64             this.x = x;
65             this.y = y;
66             this.value = value;
67         }
68 
69 
70         @Override
71         public int compareTo(Tmo o) {
72             return o.value -this.value;
73         }
74     }