You are viewing a single comment's thread. Return to all comments →
C++ BFS Simple
typedef unordered_map<int,int> graph; graph buildGraph(vector<vector<int>> &input){ graph temp; for(const auto &x : input) temp[x[0]] = x[1]; return temp; } int quickestWayUp(vector<vector<int>> ladders, vector<vector<int>> snakes) { graph ladders_graph = buildGraph(ladders); graph snakes_graph = buildGraph(snakes); vector<int> visited(101, INT_MAX/2); visited[1] = 0; queue<int> que; que.push(1); while(!que.empty()){ auto idx = que.front(); que.pop(); for(int i = 1; i <= 6 && idx + i <= 100; i++){ auto j = idx + i; if(snakes_graph.count(j)) j = snakes_graph[j]; else if(ladders_graph.count(j)) j = ladders_graph[j]; if(visited[idx] + 1 < visited[j]){ visited[j] = visited[idx] + 1; que.push(j); } } } return visited[100] == INT_MAX/2 ? -1 : visited[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 →
C++ BFS Simple