Sol using dikstra


#1

struct comparator{
bool operator() (const pair<int,int> &a, const pair<int,int> &b){
return a.second > b.second; //condition for min heap
}
};

int Solution::snakeLadder(vector<vector > &A, vector<vector > &B) {
int dp[101][101];
memset(dp,0,sizeof(dp));

//no dynamic programming used don't get confused by name dp
//array of edges each edge has wt 1
for(int i = 1; i<101;i++)
{
        for(int k = 1;k<=6;k++)
        {
            if(i+k<101)dp[i][i+k] = 1;
        }
}
for(int i = 0;i<A.size();i++)            //tuning for ladders
{
    int st = A[i][0];
    int end = A[i][1];
    for(int j = 1;j<=6;j++){
        if(st+j<101)dp[st][st+j] = 0;
    }
    for(int j = 1;j<=6;j++)
    {
        if(st-j>=1){
            dp[st-j][st] = 0;
        }
        dp[st-j][end] = 1;
    }
}
for(int i = 0;i<B.size();i++)         //tuning for snakes
{
    int st = B[i][0];
    int end = B[i][1];
    for(int j = 1;j<=6;j++){
        if(st+j<101)dp[st][st+j] = 0;
    }
    for(int j = 1;j<=6;j++)
    {
        if(st-j>=1){
            dp[st-j][st] = 0;
        }
        dp[st-j][end] = 1;
    }
}
//dikstra 
int distance[101];
for(int i = 0;i<101;i++){
    distance[i] = INT_MAX;
}
distance[1] = 0;
priority_queue<pair<int,int>,vector<pair<int,int> >,comparator> pq;
pq.push(make_pair(1,0));  //node & dist
while(pq.empty()!=true){
    pair<int,int> n = pq.top();
    int src = n.first;
    int wt = n.second;
    pq.pop();
    for(int j = 1; j<101;j++){
        if(dp[src][j]==1){
            if(distance[src]!=INT_MAX &&  wt + 1 < distance[j]){
                distance[j] = 1 + wt;
                pq.push(make_pair(j,distance[j]));
            }
        }
    }
}

if(distance[100]==INT_MAX)return -1;
return distance[100];

}