题解 | 小红的数位删除

通过位运算状态压缩解题和bfs搜索都是可行的，这里使用bfs

#include<bits/stdc++.h>
using namespace std;

struct State
{
    string sa;
    string sb;
    int steps;
};

bool check(string sa, string sb)
{
    if(sa.size()!=0 && sb.size()!=0)//由于stoll,空串会异常，所以我们先检查后转换。
    {
        long long a = stoll(sa),b= stoll(sb);
        return (a%b==0 || b%a==0);
    }
    else return false;
}

int bfs(int a,int b)
{
    queue<State> q;//队列FIFO那么最先压入的应该是我们steps==1的情况，依次类推
    q.push({to_string(a),to_string(b),0});//初始化

    set<pair<string,string>> visited;//用set去重,减少重算
    visited.insert({to_string(a),to_string(b)});
    while(q.size()!=0)
    {
        State current = q.front();
        q.pop();
        if(check(current.sa,current.sb))
        {
            return current.steps;
        }
        for(int i = 0; i < current.sa.length(); i++)
        {
            string next_a = current.sa.substr(0, i) + current.sa.substr(i + 1);
            if (visited.find({next_a, current.sb}) == visited.end()) 
            {
                visited.insert({next_a, current.sb});
                q.push({next_a, current.sb, current.steps + 1});
            }
        }
        for (int i = 0; i < current.sb.length(); i++) 
        {
            string next_b = current.sb.substr(0, i) + current.sb.substr(i + 1);
            if (visited.find({current.sa, next_b}) == visited.end()) 
            {
                visited.insert({current.sa, next_b});
                q.push({current.sa, next_b, current.steps + 1});
            }
        }
    }
    return -1;//如果列表清空仍然没有返回步数说明无法实现
}


int main()
{
    int a,b;
    cin >> a >> b;
    if(a%b==0 || b%a==0)
    {
        cout << 0 << endl;
        return 0; 
    }
    else cout << bfs(a,b) << endl;
}