【leetcode】778. 水位上升的泳池中游泳（swim-in-rising-water）（二分+DFS）[困难]

链接

https://leetcode-cn.com/problems/swim-in-rising-water/

耗时

解题：12 min
题解：9 min

题意

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？

思路

和【leetcode】1631. 最小体力消耗路径（path-with-minimum-effort）（二分+DFS）[中等] 的思路是一样的，唯一的区别是，这道题建图的边权是两相邻格点的最大值，之后完全相同，二分答案，dfs判断答案是否可行。

时间复杂度： O ( N 2 ∗ l o g N ) O(N^2*logN) O(N2∗logN)

AC代码

class Solution {
public:
    struct node {
        int to, cost;
    };
    vector<node> E[10100];
    void add_edge(int u, int v, int c) {
        E[u].push_back((node){v, c});
    }                                   
                                        
    vector<bool> vis;
    int rows = 1, columns = 1;
    int node_num = 1;
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    bool dfs(int u, int maxk) {
        if(u == node_num-1) {
            return true;
        }
        vis[u] = true;
        for(int i = 0; i < E[u].size(); ++i) {
            int to = E[u][i].to;
            if(vis[to]) continue;
            if(E[u][i].cost <= maxk) {
                bool flag = dfs(to, maxk);
                if(flag) return true;
            }
        }
        return false;
    }         
                                        
    bool check(int maxk) {
        vis.assign(10100, false);
        return dfs(0, maxk);
    }
                                        
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        rows = grid.size();
        columns = grid[0].size();
        
        // build graph
        for(int i = 0; i < rows; ++i) {
            for(int j = 0; j < columns; ++j) {
                int sou = i*columns+j;
                for(int d = 0; d < 4; ++d) {
                    int x = i + dir[d][0];
                    int y = j + dir[d][1];
                    if((x >= 0 && x <= rows-1) && (y >= 0 && y <= columns-1)) {
                        int des = x*columns+y;
                        int cost = max(grid[x][y], grid[i][j]);
                        add_edge(sou, des, cost);
                    }
                }
            }
        }
        
        node_num = (rows-1)*columns+columns;
        
        // binary search
        int s = max(grid[0][0], grid[rows-1][columns-1]), t = n*n-1;
        while(s < t) {
            int m = ((s+t)>>1);
            if(check(m)) t = m;
            else s = m+1;
        }
        return s;
    }
};