Solution using Dijkstra's algorithm


#1
bool check(int i, int j, int n, int m)
{
    return i>=0 && i=0 && j<m;
}
int Solution::solve(vector<vector > &A) {
    int n = (int)A.size();
    int m = (int)A[0].size();
    priority_queue<pair<int,pair<int,int>>> pq;
    vector<vector<int>> dist(n, vector (m,INT_MAX));
    dist[0][0] = 1;
    pq.push({1,{0,0}});
    int maxx = 1;
    while(!pq.empty())
    {
        pair<int,pair<int,int>> p = pq.top();
        pq.pop();
        int c = p.first;
        int i = p.second.first;
        int j = p.second.second;
        if(check(i+1,j,n,m) && A[i+1][j] > A[i][j] && dist[i+1][j] > c + 1)
        {
            dist[i+1][j] = c + 1;
            maxx = max(maxx, dist[i+1][j]);
            pq.push({dist[i+1][j],{i+1,j}});
        }
        if(check(i,j+1,n,m) && A[i][j+1] > A[i][j] && dist[i][j+1] > c + 1)
        {
            dist[i][j+1] = c + 1;
            maxx = max(maxx, dist[i][j+1]);
            pq.push({dist[i][j+1],{i,j+1}});
        }
    }
    return dist[n-1][m-1] == INT_MAX ? -1 : dist[n-1][m-1];
}