778. Swim in Rising Water

题目

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

算法分析及题解

对题目进行分析后发现，海平面不断上升的过程，其实就是一个以(0,0)为起点的无向图不断扩充的过程。而当(N-1,N-1)也在该图内时，此时的海平面即为所求结果。再经过简单的分析，问题 “求点(N-1, N-1)可达时海平面的高度”可被分解为以下步骤解决：

1. 给定海平面高度（初始为0），点 (N-1, N-1) 是否可达
2. 若1判断不可达，海平面+1，回到1判断
3. 若1判断可达，返回当前海平面高度，程序结束

23步很好表达：

int swimInWater(vector<vector<int>>& grid) {
        int elevation = 0;
        while(!update(grid, elevation)){
            elevation ++;
        }
        return elevation;
    }
//elevation: 海平面高度
//update(): 给定海平面，判断(N-1, N-1) 是否可达

关键的问题就在于第一个步骤，怎么在给定的海平面高度里判断 (N-1, N-1) 是否可达，也即 update()函数该怎么写

Update函数

update()函数要解决的问题就是：给定正方形地图数据、当前海平面高度，判断 (N-1, N-1)是否可达。这里的图其实是一个类隐式图，正方形地图内点是否在图内是需要在搜索过程中进行判断的。那为什么说它是类隐式图呢？因为这个无向图里的点的域是确认的：从 (0,0) 到 (N-1, N-1)，因此如果不考虑性能，可以先遍历两次构造出无向图，然后再从(0,0)去遍历，也是可行的。当然这里为了性能不考虑这种算法。

bool update(vector<vector<int>>& grid, int elevation){
            //N:正方形地图边长
        int N = grid.size();
            //mark：图结点访问标记
        bool** mark = new bool*[N];
        for(int i = 0; i < N; ++i){
            mark[i] = new bool[N];
            for(int e = 0; e < N; ++e)
                mark[i][e] = false;
        }

        //搜索

        //清理内存
        bool result = mark[N-1][N-1];
        for(int i = 0; i < N; ++i){
            delete[] mark[i];
        }
        delete[] mark;
        return result;
    }

注意到update()函数中 搜索 部分还是空缺的，这里有两种解法，DFS和BFS

DFS实现搜索

void DFS(vector<vector<int>>& grid, int elevation, bool** mark, int x, int y){
        int N = grid.size();
        if(mark[x][y]) return;

        if(grid[x][y] <= elevation){
            mark[x][y] = true;
            if(x+1 < N) DFS(grid,elevation,mark,x+1,y);
            if(x-1 >= 0) DFS(grid,elevation,mark,x-1,y);
            if(y+1 < N) DFS(grid,elevation,mark,x,y+1);
            if(y-1 >= 0) DFS(grid,elevation,mark,x,y-1);
        }
    }

对应在update()函数内的搜索语句：

//搜索
DFS(grid, elevation, mark, 0, 0);

BFS实现搜索

void BFS(vector<vector<int>>& grid, int elevation, bool** mark, int sx, int sy){
        if(grid[sx][sy] > elevation) return;
        
        int N = grid.size();
        pair<int, int> source = make_pair(sx,sy);
        queue< pair<int, int> > q;
        q.push(source);
        while(!q.empty()){
            pair<int, int> now = q.front();
            q.pop();
            int x = now.first, y = now.second;
            mark[x][y] = true;

            if(x-1 >= 0 && !mark[x-1][y] && grid[x-1][y] <= elevation)
                q.push(make_pair(x-1,y));
            if(x+1 < N && !mark[x+1][y] && grid[x+1][y] <= elevation)
                q.push(make_pair(x+1,y));
            if(y-1 >= 0 && !mark[x][y-1] && grid[x][y-1] <= elevation)
                q.push(make_pair(x,y-1));
            if(y+1 < N && !mark[x][y+1] && grid[x][y+1] <= elevation)
                q.push(make_pair(x,y+1));
        }
    }

对应在update()函数内的搜索语句：

//搜索
BFS(grid, elevation, mark, 0, 0);

这时候问题出现了：某一些测例出现了超时。

BFS 优化

考虑可能pair和queue占用了一些时间，因此优化了一下代码

void BFS(vector<vector<int>>& grid, int elevation, bool** mark, int sx, int sy){
        if(grid[sx][sy] > elevation) return;

        int N = grid.size();
        queue<int> q;
        q.push(sx*N+sy);
        while(!q.empty()){
            int now = q.front();
            q.pop();
            int x = now/N, y = now%N;
            mark[x][y] = true;

            if(x-1 >= 0 && !mark[x-1][y] && grid[x-1][y] <= elevation)
                q.push((x-1)*N+y);
            if(x+1 < N && !mark[x+1][y] && grid[x+1][y] <= elevation)
                q.push((x+1)*N+y);
            if(y-1 >= 0 && !mark[x][y-1] && grid[x][y-1] <= elevation)
                q.push(x*N+y-1);
            if(y+1 < N && !mark[x][y+1] && grid[x][y+1] <= elevation)
                q.push(x*N+y+1);
        }
    }

但是问题仍然存在。经过测试研究发现，BFS所经历的update次数要大于DFS，说明求路径存在而不是求最短路的时候采用DFS是更好的算法。