---
# System prepended metadata

title: 0778. Swim in Rising Water
tags: [Leetcode, BFS, FaceBook, Priority Queue, Hard]

---

# 0778. Swim in Rising Water
###### tags: `Leetcode` `FaceBook` `Hard` `BFS` `Priority Queue`
Link: https://leetcode.com/problems/swim-in-rising-water/
## 思路
找所有左上到右下的路径里面最小的最大值
和[1102. Path With Maximum Minimum Value](https://hackmd.io/QjOZ8IEyRTOJiMtn94A1FQ)差不多的思路
bfs+priority queue
每次找最小值
## Code
```java=
class Solution {
    public int swimInWater(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(grid[a[0]][a[1]]-grid[b[0]][b[1]]));
        pq.add(new int[]{0,0});
        visited[0][0] = true;
        int ans = grid[0][0];
        
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            ans = Math.max(ans, grid[curr[0]][curr[1]]);
            if(curr[0]==m-1 && curr[1]==n-1) return ans;
            
            for(int[] dir:dirs){
                int nextx = curr[0]+dir[0];
                int nexty = curr[1]+dir[1];
                if(nextx>=0 && nextx<m && nexty>=0 && nexty<m && !visited[nextx][nexty]){
                    int[] next = new int[]{nextx, nexty};
                    visited[nextx][nexty] = true;
                    pq.add(next);
                }
            }
        }
        
        return ans;
    }
}
```