LeetCode 778. Swim in Rising Water

题目链接：https://leetcode.com/problems/swim-in-rising-water/

题意：已知一个n*n的网格，初始时的位置为(0,0)，目标位置为(n-1,n-1)，且在t时刻，只有当网格中的值小于等于t时才能移动到该网格，且移动时只有上下左右四个方向。输出到网格(n-1,n-1)的最短时间。

思路：dfs一下即可，记录一个dp数组，表示到该网格的最小时间，开始时每个网格都设为无穷大，每次更新时间t为当前格子的值与上一时间的较大值。当周围网格的最小时间比当前网格大时则继续搜索。这样保证了网格值大的都能被搜到，且t小的不再搜索

class Solution {

public:

    //四个方向

    int dx[4]={0,0,1,-1};

    int dy[4]={1,-1,0,0};

    void dfs(int x,int y,int t,vector<vector<int> > &grid,vector<vector<int> > &dp){

        dp[x][y]=max(t,grid[x][y]);

        for(int i=0;i<4;i++){

            int x0=x+dx[i],y0=y+dy[i];

            if(x0<dp.size()&&x0>=0&&y0<dp.size()&&y0>=0){

                if(dp[x0][y0]<=dp[x][y]){ //如果下一个网格的最短时间比当前网格小，则不搜索

                continue;

                }

            dfs(x0,y0,dp[x][y],grid,dp);

            }

        }

    }

    int swimInWater(vector<vector<int>>& grid) {

        vector<vector<int> > dp(grid.size(),vector<int>(grid.size(),1e9));

        //初始时t为第一个网格的值

        dfs(0,0,grid[0][0],grid,dp);

        return dp[grid.size()-1][grid.size()-1];

    }

};

上述算法复杂度较高，可以通过优先队列优化，优先队列中存储每个网格的信息，按照网格值较小优先。从初始网格开始，每次将队列头的网格弹出，并标记（每个网格访问一次）。并对其周围四个网格中未访问的入队。在此过程中，不断更新t的大小，取$t=max(t,grid[x][y])$。直到目标网格。

class Solution {

public:

    struct P{

        int x,y,z;

        //按照grid[x][y]从小到大排列

        bool operator <(const P& t)const {

            return z>t.z;

        }

    };

    int dx[4]={0,0,1,-1};

    int dy[4]={1,-1,0,0};

    int swimInWater(vector<vector<int>>& grid) {

        //记录是否遍历过

        vector<vector<bool> > vis(grid.size(),vector<bool>(grid.size(),0));

        priority_queue<P> q;

        P a;

        a.x=0,a.y=0,a.z=0;

        vis[0][0]=1;

        q.push(a);  //起始网格

        int t=grid[0][0];

        while(!q.empty()){

            a= q.top();q.pop();

            vis[a.x][a.y]=1;

            if(a.x==grid.size()-1&&a.y==grid.size()-1) //到达目标网格，退出

                return max(t,grid[a.x][a.y]);

            if(a.z>t) //更新t

                t=a.z;

            for(int i=0;i<4;i++){ //将周围未访问的网格入队

            int x0=a.x+dx[i],y0=a.y+dy[i];

            if(x0<grid.size()&&x0>=0&&y0<grid.size()&&y0>=0&&vis[x0][y0]==0){

                P b;

                vis[x0][y0]=1;

                b.x=x0,b.y=y0,b.z=grid[x0][y0];

                q.push(b);

            }

        }

        }

       return 0;

    }

};

巴特西

LeetCode 778. Swim in Rising Water

最新文章

热门文章