解法一：题目可以理解为从(0,0)到(n-1,n-1)的所有路径的最大海拔的最小值,max(路径最大海拔)。那么对于每一个点，求从(0 , 0)到该点的所有路径的最大值的最小值。可以用bfs来做，用maxele存储从(0,0)到该点的路径中的最大值的最小值，用inque防止cell在队列中重复存在；
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size() ;
vector<vector<int>> inque(n , vector<int>(n , 0)) , maxele(n , vector<int>(n , INT_MAX)) ;
queue<int> q ;
q.push(0) ;
inque[0][0] = 1 ;
maxele[0][0] = grid[0][0] ;
while(!q.empty())
{
int i = q.front() / n , j = q.front() % n ;
q.pop() ;
inque[i][j] = 0 ;
for(int k = 0 ; k < 4 ; k++)
{
int ni = i + dir[k] , nj = j + dir[k+1] ;
if(ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
if(max(maxele[i][j] , grid[ni][nj]) < maxele[ni][nj])
{
maxele[ni][nj] = max(maxele[i][j] , grid[ni][nj]) ;
if(!inque[ni][nj])
{
q.push(ni * n + nj) ;
inque[ni][nj] = 1 ;
}
}
}
}
return maxele[n-1][n-1];
}
private:
vector<int> dir = {-1, 0 , 1, 0 , -1};
};
解法二：
cell中的海拔是[0 , N*N - 1]的排列，所以所求的least time一定处于[0 , N*N-1]的范围内，可以使用二分搜索；给定x，如果找到一条路径，路径中的每一个cell的海拔都小于或等于x，则r = x ;否则l = x + 1 ;(路径搜索可以用dfs或者bfs)
dfs(使用dfs一定要记得写上递归基)(时间复杂度(O(N^2log(N^2))) , 8ms.因为只搜索一条可行路径，不需要遍历所有路径，相较bfs更快）
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size() ;
int l = grid[0][0] , r = n * n - 1 ;
while(l < r)
{
int mid = l + (r - l) / 2;
if(valid(mid , grid)) r = mid ;
else l = mid + 1 ;
}
return l ;
}
private:
vector<int> dir = {-1 , 0 , 1 , 0 , -1};
bool valid(int x , vector<vector<int>>& grid)
{
int n = grid.size() ;
vector<vector<int>> visited(n , vector<int>(n , 0));
return dfs(0 , 0 , x , visited , grid) ;
}
bool dfs(int r , int c , int x , vector<vector<int>>& visited , vector<vector<int>> &grid)
{
int n = grid.size() ;
if(r == n - 1 && c == n - 1) return true ;
visited[r][c] = 1 ;
for(int k = 0 ; k < 4 ; k++)
{
int nr = r + dir[k] , nc = c + dir[k+1] ;
if(nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc] || grid[nr][nc] > x) continue ;
if(dfs(nr , nc , x , visited , grid)) return true;
}
return false;
}
};
bfs（28ms)
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size() ;
int l = grid[0][0] , r = n * n - 1 ;
while(l < r)
{
int mid = l + (r - l) / 2;
if(bfs(mid , grid)) r = mid ;
else l = mid + 1 ;
}
return l ;
}
private:
vector<int> dir = {-1 , 0 , 1 , 0 , -1};
bool bfs(int x , vector<vector<int>>& grid)
{
int n = grid.size() ;
vector<vector<int>> visited(n , vector<int>(n , 0));
queue<int> q ;
q.push(0) ;
visited[0][0] = 1 ;
while(!q.empty())
{
int r = q.front() / n , c = q.front() % n ;
q.pop() ;
if(r == n - 1 && c == n - 1) return true ;
for(int k = 0 ; k < 4 ; k++)
{
int nr = r + dir[k] , nc = c + dir[k + 1];
if(nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc] || grid[nr][nc] > x) continue ;
visited[nr][nc] = 1 ;
q.push(nr * n + nc) ;
}
}
return false;
}
};
解法三：在搜索路径的过程中，我们优先选择目前为止搜索到的海拔最小的cell继续搜索，因为每个cell可以往四个方向搜索，所以任意两个cell都连通。所以可以用贪心的方法做， 如果不是任意两个cell都连通，就不能用贪心来做；
priority_queue , 在用priority_queue或者queue或者deque或stack的时候，记得要pop；（32ms）
class Solution {
public:
int swimInWater(vector<vector<int>>& grid)
{
int res = grid[0][0] , n = grid.size();
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> > q ;
vector<vector<int>> vis(n , vector<int>(n , 0)) ;
vector<int> dir = {-1 , 0 , 1 , 0 , -1} ;
q.push({0 , 0}) ;
vis[0][0] = 1 ;
while(!q.empty())
{
int t = q.top().first , r = q.top().second / n , c = q.top().second % n ;
q.pop() ;
res = max(res , t) ;
if(r == n - 1 && c == n - 1) break ;
for(int k = 0 ; k < 4 ; k++)
{
int nr = r + dir[k] , nc = c + dir[k + 1] ;
if(nr < 0 || nr >= n || nc < 0 || nc >= n || vis[nr][nc]) continue;
q.push({grid[nr][nc] , nr * n + nc}) ;
vis[nr][nc] = 1 ;
}
}
return res;
}
};
leetcode 778. Swim in Rising Water
原文：https://www.cnblogs.com/mychen06/p/12602866.html