【BFS】数对

题目

试题 算法提高 数对

---

对于有序数对 $(x,y)$ ，每次操作可以用 $(x+y) \%100$ 或 $x$ 和 $y$ 的最大公约数 替换掉 $x$ 或 $y$ 。

即一次操作可将 $(x,y)$ 转换为 $((x+y)\%100,y)$ 、 $(x,(x+y)$ 、 $(gcd(x,y),y)$ 、$(x,gcd(x,y))$ 之一。

求将有序数对 $(a,b)$ 转换为 $(c,d)$ 最少需要几次操作。

输入

$4$ 个非负整数 $a,b,c,d$ 。

输出

输出一个整数表示答案，如果无解输出 $-1$ 。

样例输入

1 1 2 1

样例输出

1

数据规模和约定

• $0\le a,b,c,d<100$

解题

方法一：BFS

思路

这题数据范围比较小，合法的数字对最多也就 $100 \times 100 = 10000$ 对，DFS 和 BFS 都能做，考虑到要求最少操作次数就用 BFS 吧。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int a, b, c, d;

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        a = in.nextInt(); b = in.nextInt();
        c = in.nextInt(); d = in.nextInt();
        Queue<int[]> que = new LinkedList<>();
        boolean[][] vis = new boolean[110][110];
        que.offer(new int[]{a, b});
        vis[a][b] = true;
        int step = 0;
        while (!que.isEmpty()) {
            int sz = que.size();
            while (sz-- > 0) {
                int[] curr = que.poll();
                a = curr[0]; b = curr[1];
                if (a == c && b == d) {
                    System.out.println(step);
                    return;
                }
                int x = (a + b) % 100, y = gcd(a, b);
                if (!vis[x][b]) {
                    que.offer(new int[]{x, b});
                    vis[x][b] = true;
                }
                if (!vis[a][x]) {
                    que.offer(new int[]{a, x});
                    vis[a][x] = true;
                }
                if (!vis[y][b]) {
                    que.offer(new int[]{y, b});
                    vis[y][b] = true;
                }
                if (!vis[a][y]) {
                    que.offer(new int[]{a, y});
                    vis[a][y] = true;
                }
            }
            ++step;
        }
        System.out.println(-1);
    }
}