-
Notifications
You must be signed in to change notification settings - Fork 0
/
Main12761.java
91 lines (82 loc) · 2.09 KB
/
Main12761.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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main12761 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] bridge = new int[100000 + 1];
Arrays.fill(bridge, 100000);
bridge[N] = 0;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(N);
while (!q.isEmpty()) {
int p = q.poll();
if (p + 1 <= 100000 && bridge[p] + 1 < bridge[p + 1]) {
bridge[p + 1] = bridge[p] + 1;
if (p +1 == M) {
break;
}
q.offer(p + 1);
}
if (p - 1 >= 0 && bridge[p] + 1 < bridge[p - 1]) {
bridge[p - 1] = bridge[p] + 1;
if (p -1 == M) {
break;
}
q.offer(p - 1);
}
if (p + A <= 100000 && bridge[p] + 1 < bridge[p + A]) {
bridge[p + A] = bridge[p] + 1;
if (p +A== M) {
break;
}
q.offer(p + A);
}
if (p - A >= 0 && bridge[p] + 1 < bridge[p - A]) {
bridge[p - A] = bridge[p] + 1;
if (p -A== M) {
break;
}
q.offer(p - A);
}
if (p + B <= 100000 && bridge[p] + 1 < bridge[p + B]) {
bridge[p + B] = bridge[p] + 1;
if (p +B== M) {
break;
}
q.offer(p + B);
}
if (p - B >= 0 && bridge[p] + 1 < bridge[p - B]) {
bridge[p - B] = bridge[p] + 1;
if (p -B== M) {
break;
}
q.offer(p - B);
}
if (p != 0 && p * A <= 100000 && bridge[p] + 1 < bridge[p * A]) {
bridge[p * A] = bridge[p] + 1;
if (p *A== M) {
break;
}
q.offer(p * A);
}
if (p * B != 0 && p * B <= 100000 && bridge[p] + 1 < bridge[p * B]) {
bridge[p * B] = bridge[p] + 1;
if (p *B== M) {
break;
}
q.offer(p * B);
}
}
System.out.println(bridge[M]);
}
}