Snakes and Ladders: The Quickest Way Up

  • + 0 comments
    int quickestWayUp(vector<vector<int>> ladders, vector<vector<int>> snakes) 
    {
        set<int> snakePoints;
        for(auto it : snakes)
        {
            snakePoints.insert(it[0]);
        }
        vector<vector<pair<int,int>>> adj(101);
        for(int i=1 ; i<=99 ; i++) //rolling dice
        {
            if(snakePoints.find(i)==snakePoints.end())
            {
                for(int j=1 ; j<=6 && (i+j)<=100 ; j++)
                {
                    adj[i].push_back({(i+j),1});
                }
            }
        }
        for(auto it : ladders) //ladders
        {
            adj[it[0]].push_back({it[1],0});
        }
        for(auto it : snakes) //snakes
        {
            adj[it[0]].push_back({it[1],0});
        }
        vector<int> distance(101,INT_MAX);
        distance[1]=0;
        set<pair<int,int>> myset;
        myset.insert({0,1});
        while(myset.size()>0)
        {
            pair<int,int> temp=*myset.begin();
            int dist2=temp.first;
            int node=temp.second;
            myset.erase(myset.begin());
            for(auto it : adj[node])
            {
                if(dist2+it.second<distance[it.first])
                {
                    distance[it.first]=dist2+it.second;
                    myset.insert({dist2+it.second,it.first});
                }
            }
        }
        if(distance[100]==INT_MAX)
        {
            return -1;
        }
        return distance[100];
    }