# 1345. Jump Game IV
###### tags: `Leetcode` `Hard` `BFS`
Link: https://leetcode.com/problems/jump-game-iv/
## 思路
先用map收集所有的一样的值的index集合
然后用bfs找最短路径
tricky的地方在于每个map的entry对应的list用过一遍之后就可以清空

## Code

class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
Map<Integer, List<Integer>> map = new HashMap<>();
int idx = 0;
for(int i=0; i<arr.length; i++){
int num = arr[i];
if(!map.containsKey(num)){
map.put(num, new ArrayList<Integer>());
}
map.get(num).add(i);
}

boolean[] visited = new boolean[arr.length];
Queue<Integer> q = new LinkedList<>();
q.add(0);
visited[0] = true;
int step = 0;
while(!q.isEmpty()){
int size = q.size();
for(int i=0; i<size; i++){
idx = q.poll();
if(idx == arr.length-1) return step;
if(idx-1>=0 && !visited[idx-1]){
visited[idx-1] = true;
q.add(idx-1);
}
if(idx+1<arr.length && !visited[idx+1]){
visited[idx+1] = true;
q.add(idx+1);
}
for(int next:map.get(arr[idx])){
if(!visited[next]){
visited[next] = true;
q.add(next);
}
}
map.get(arr[idx]).clear();
}
step++;
}
return step;
}
}