|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- #include <bits/stdc++.h>
- using namespace std;
- const int N=1e9+10;
- typedef long long ll;
- #define INF 0x3f3f3f3f
- #define x first
- #define y second
- // typedef pair<int,int>p;
- int dx[]={-1,0,1,0},dy[]={0,-1,0,1}; //上左下右
- // 使用dfs减枝
- string a,b;
- vector<pair<int,string>>A,B;
- unordered_map<string ,bool >st; //表示字符串的状态
- void dfs(string a,vector<pair<int,string>>&v,int l) //表示从0开始
- {
- st[a]=true;
- v.push_back({l,a});
- for(int i=0;i<a.length();i++)
- {
- string t=a.substr(0,i)+a.substr(i+1);
- if(st[t]||t=="")continue;
- dfs(t,v,l+1);
- }
-
- }
- bool check(string a,string b)
- {
- int a1=stoi(a);
- int b1=stoi(b);
- if(a1%b1==0||b1%a1==0)return true;
- return false;
- }
- void solve()
- {
- cin>>a>>b;
- dfs(a,A,0);
- st.clear();
- dfs(b,B,0);
- int ans=INF;
- for(auto a1:A)
- {
- for(auto b1:B)
- {
- if(check(a1.second,b1.second))
- {
- ans=min(ans,a1.first+b1.first);
- }
- }
- }
- cout<<(ans==INF?-1:ans);
-
-
-
-
- }
- int main()
- {
- int t;
- t=1;
- while(t--)
- {
- solve();
- }
- }
- //可以用二进制去做,但是不会,到时候再去补
复制代码
dfs函数是删除字符串的操作,不太懂,还有为什么要l+1; |
|