Snakes and Ladders: The Quickest Way Up
- Time : O(1) //constant
- Space : O(1) //constant
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| int quickestWayUp(vector<vector<int>> ladders, vector<vector<int>> snakes) {
int res = 1;
queue<int> q;
bool vis[101] = {};
unordered_map<int, int> mp;
for(auto& l : ladders) mp[l[0]] = l[1];
for(auto& s : snakes) mp[s[0]] = s[1];
q.push(1);
vis[1] = true;
while(!q.empty()) {
int sz = q.size();
while(sz--) {
auto& now = q.front(); q.pop();
for(int i = 1; i <= 6; i++) {
int nxt = now + i;
if(vis[nxt]) continue;
while(mp.count(nxt) and !vis[nxt]) {
vis[nxt] = true;
nxt = mp[nxt];
}
if(nxt == 100) return res;
vis[now + i] = true;
q.push(nxt);
}
}
res++;
}
return -1;
}
|
