侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【BFS】数对

GabrielxD
2023-04-15 / 0 评论 / 0 点赞 / 111 阅读 / 491 字
温馨提示:
本文最后更新于 2023-04-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 数对


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

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

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

输入

44 个非负整数 a,b,c,da,b,c,d

输出

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

样例输入

1 1 2 1

样例输出

1

数据规模和约定

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

解题

方法一:BFS

思路

这题数据范围比较小,合法的数字对最多也就 100×100=10000100 \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);
    }
}
0

评论区