-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
909.java
95 lines (86 loc) · 2.95 KB
/
909.java
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
__________________________________________________________________________________________________
sample 2 ms submission
class Solution {
public int snakesAndLadders(int[][] board) {
int N = board.length;
boolean[] visited = new boolean[N * N];
Queue<Integer> queue = new LinkedList<>();
int steps = 1;
queue.add(0); visited[0] = true;
int target = N * N - 1;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; ++i){
int v = queue.poll();
for(int j = 1; j <= 6; ++j){
++v;
if(visited[v]) continue;
visited[v] = true;
if(v == target) return steps;
int x = N - 1 - v / N, y = ((v / N) % 2 == 0? (v % N): (N - 1 - v % N));
if(board[x][y] < 0)
queue.add(v);
else{
if(board[x][y] == target + 1) return steps;
if(!visited[board[x][y] - 1])
queue.add(board[x][y] - 1);
}
}
}
++steps;
}
return -1;
}
}
__________________________________________________________________________________________________
sample 38676 kb submission
class Solution {
public int snakesAndLadders(int[][] board) {
if(board==null || board.length==0)
return -1;
Set<Integer> seen=new HashSet<Integer>();
Queue<Integer> queue = new LinkedList();
queue.offer(1);
seen.add(1);
queue.offer(null);
int m = board.length;
int n=board[0].length;
int step = 0;
while(!queue.isEmpty()){
Integer current = queue.poll();
if(current == null){
step++;
if(!queue.isEmpty()){
queue.offer(null);
}
continue;
}
if(current == m*n){
return step;
}
for(int i=1; i<=6; i++){
int next = current + i;
if(next>m*n)
continue;
int[] pos = getPos(next,n,n);
if(board[pos[0]][pos[1]]!=-1){
next = board[pos[0]][pos[1]];
}
if(seen.contains(next)){
continue;
}
queue.offer(next);
seen.add(next);
}
}
return -1;
}
//map id to x,y coordinates
int[] getPos(int id, int m, int n){
id--;
int row = (id)/n;
int col = row%2==0?(id)%n: (n-1-id%n);
return new int[]{n-1-row, col};
}
}
__________________________________________________________________________________________________