2022/8/20网易研发笔试

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String line = cin.nextLine();
        String[] nums = line.split(" ");
        if (check(nums[0], nums[1])) {
            System.out.println(0);
            return;
        }

        Queue<String> queue = new ArrayDeque<>();
        Set<String> seen = new HashSet<>();
        queue.offer(nums[0]);
        queue.offer(nums[1]);
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            size >>= 1;
            for (int i = 0; i < size; i++) {
                String A = queue.poll();
                String B = queue.poll();

                if (A.length() > 1)
                    for (int k = 0; k < A.length(); k++) {
                        String newA = A.substring(0, k) + A.substring(k + 1);
                        String key = getKey(newA, B);
                        if (seen.contains(key))
                            continue;
                        seen.add(key);
                        if (check(newA, B)) {
                            System.out.println(step + 1);
                            return;
                        }
                        queue.offer(newA); queue.offer(B);
                    }

                if (B.length() > 1)
                    for (int k = 0; k < B.length(); k++) {
                        String newB = B.substring(0, k) + B.substring(k + 1);
                        String key = getKey(A, newB);
                        if (seen.contains(key))
                            continue;
                        seen.add(key);
                        if (check(A, newB)) {
                            System.out.println(step + 1);
                            return;
                        }
                        queue.offer(A); queue.offer(newB);
                    }
            }

            step++;
        }

        System.out.println(-1);
    }

    public static String getKey(String A, String B) {
        return A.compareTo(B) <= 0 ? A + B : B + A;
    }

    public static boolean check(String A, String B) {
        int a = Integer.parseInt(A);
        int b = Integer.parseInt(B);
        if (a == 0 || b == 0)
            return true;

        return a % b == 0 || b % a == 0;
    }
}