一. 题目

二. 思路

三. 代码

const int N=760, INF=numeric_limits<int>::max();

class Dijkstra
{
public:
    class Node
    {
    public:
        int x, y, d;
    public:
        Node(int x_, int y_, int d_):x(x_), y(y_), d(d_) {}

        bool operator < (const Node &t) const
        {
            return d>t.d;
        }
    };

public:
    bool st[N][N];
    priority_queue<Node> q;
    int dist[N][N];
    int dx[4]={0, -1, 0, 1};
    int dy[4]={-1, 0, 1, 0};

public:
    void init()
    {
        fill(&st[0][0], &st[0][0]+N*N, false);
        fill(&dist[0][0], &dist[0][0]+N*N, INF);
        while(!q.empty()) q.pop();
    }

    int work(vector<vector<int>>& moveTime, int n, int m)
    {
        dist[0][0]=0, q.emplace(0, 0, 0);
        while(!q.empty())
        {
            Node t=q.top();
            q.pop();

            int x=t.x, y=t.y, d=t.d;
            if(x==n-1&&y==m-1) return dist[n-1][m-1];
            if(d>dist[x][y]||st[x][y]) continue;
            st[x][y]=true;

            for(int i=0;i<4;++i)
            {
                int a=x+dx[i], b=y+dy[i];
                if(a<0||a>n-1||b<0||b>m-1) continue;

                int newDist=max(d, moveTime[a][b])+(x+y)%2+1;
                if(newDist>=dist[a][b]) continue;
                dist[a][b]=newDist, q.emplace(a, b, newDist);
            }
        }
        return dist[n-1][m-1];
    }
}d;

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        d.init();
        return d.work(moveTime, moveTime.size(), moveTime[0].size());
    }
};