You are viewing a single comment's thread. Return to all 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]; }
Seems like cookies are disabled on this browser, please enable them to open this website
Snakes and Ladders: The Quickest Way Up
You are viewing a single comment's thread. Return to all comments →