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
58
59 | package SnakeLadder;
import java.util.*;
public class Main {
static int N;// number of cells
static int[] moves;// end of snake or ladder
public static void main(String[] args) {
N = 30;
moves = new int[N];
Arrays.fill(moves, -1);
// Ladders
moves[2] = 21;
moves[4] = 7;
moves[10] = 25;
moves[19] = 28;
// Snakes
moves[26] = 0;
moves[20] = 8;
moves[16] = 3;
moves[18] = 6;
int p = getMinPath();
System.out.println(p);
}
static int getMinPath(){
Queue<Integer> que = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
que.add(0);
visited.add(0);
int path = 0;
while(!que.isEmpty()){
int sz = que.size();
for(int i=0; i<sz; ++i){
int cell = que.poll();
if(cell==(N-1)) return path;
for(int k=1; k<=6; ++k){
if(cell+k<N && !visited.contains(cell+k)){
que.add(cell+k);
visited.add(cell+k);
if(moves[cell+k]>=0){
que.add(moves[cell+k]);
visited.add(moves[cell+k]);
}
}
}
}
path++;
}
return path;
}
}
|
No comments:
Post a Comment