/
1345. Jump Game IV.cpp
57 lines (46 loc) · 1.33 KB
/
1345. Jump Game IV.cpp
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// https://leetcode.com/problems/jump-game-iv/
class Solution
{
public:
int minJumps(vector<int> &arr)
{
if (arr.size() == 1)
return 0;
int result = 0;
queue<int> q;
unordered_map<int, vector<int>> mp;
for (int i = 0; i < arr.size(); i++)
mp[arr[i]].push_back(i);
q.push(0);
while (!q.empty())
{
result++;
int size = q.size();
for (int i = 0; i < size; ++i)
{
int a = q.front();
q.pop();
if (a - 1 >= 0 && mp.find(arr[a - 1]) != mp.end())
q.push(a - 1);
if (a + 1 < arr.size() && mp.find(arr[a + 1]) != mp.end())
{
if (a + 1 == arr.size() - 1)
return result;
q.push(a + 1);
}
if (mp.find(arr[a]) != mp.end())
{
for (auto k : mp[arr[a]])
if (k != a)
{
if (k == arr.size() - 1)
return result;
q.push(k);
}
}
mp.erase(arr[a]);
}
}
return result;
}
};