AcWing 3671. 走路还是坐公交
原题链接
简单
作者:
bakanoko
,
2025-04-01 22:19:07
·广东
,
所有人可见
,
阅读 1
注意输入的方式
import java.math.*;
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static void main(String[] args) throws IOException {
Solution s = new Solution();
s.solve(read, out);
}
}
class Solution{
public Solution(){}
static int N = (int)1e5 + 3;
int[] d = new int[N];
int n, k;
int[] dx = {-1, 1};
int bfs() {
Arrays.fill(d, -1);
Queue<Integer> q = new ArrayDeque<>();
d[n] = 0;
q.add(n);
while (!q.isEmpty()) {
int p = q.remove();
int x = 0;
for (int i = 0; i < 3; i++) {
if (i == 2) {
x = p * 2;
if (x >= 1 && x < N && d[x] == -1) {
d[x] = d[p] + 1;
q.add(x);
}
}else {
x = p + dx[i];
if (x >= 1 && x < N && d[x] == -1) {
d[x] = d[p] + 1;
q.add(x);
}
}
}
}
return d[k];
}
public void solve (BufferedReader read, PrintWriter out) throws IOException {
String s;
while ((s = read.readLine()) != null) {
String[] ss = s.split(" ");
n = Integer.valueOf(ss[0]);
k = Integer.valueOf(ss[1]);
out.println(bfs());
}
out.flush();
}
}
class Test{
public Test(){};
public void test () {
}
}