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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, k;
static int visited[] = new int[100001];
static int dx[] = {-1,1,2};
static int ans = 987654321;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); //수빈의 위치
k = Integer.parseInt(st.nextToken()); //동생의 위치
for (int i = 0; i < 100001; i++) visited[i] = -1;
bfs(n, k);
System.out.println(ans);
}
static void bfs(int start, int dest) {
Queue<Pos> q = new LinkedList<>();
q.add(new Pos(start, 0));
visited[start] = -2;
while(!q.isEmpty()) {
int now = q.peek().x;
int cnt = q.peek().cnt;
q.poll();
if (now == dest) {
ans = ans > cnt ? cnt : ans;
break;
}
for (int i = 0; i < 3; i++) {
int nx = now;
if (i == 2) nx *= 2;
else nx += dx[i];
if (nx < 0 || nx > 100000 || visited[nx] != -1) continue;
visited[nx] = now;
q.add(new Pos(nx, cnt+1));
}
}
}
static class Pos {
int x, cnt;
public Pos(int x, int cnt) {
this.x = x;
this.cnt = cnt;
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
BOJ/JAVA