dfs问题
#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=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=="")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； 在dfs问题中，使用DFS（深度优先搜索）可以遍历所有可能的解空间。但是在实际应用中，为了提高效率，我们需要进行剪枝操作。
下面是一个使用DFS减枝的例子，其中通过交换字符串中的两个字符，找出最小操作次数使得两个字符串相等。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<string, bool> st; //表示字符串的状态
int ans = INT_MAX;
void dfs(string a, vector<pair<int, string>>& v, int l) //表示从0开始
{
if (st) return;
st = true;
v.push_back({l, a});
for (int i = 0; i < a.size(); i++)
{
for (int j = i + 1; j < a.size(); j++)
{
swap(a, a);
dfs(a, v, l + 1);
swap(a, a); //恢复现场
}
}
v.pop_back();
st = false;
}
bool check(string a, string b)
{
return a == b;
}
int main()
{
string a, b;
cin >> a >> b;
vector<pair<int, string>> A, B;
dfs(a, A, 0);
st.clear();
dfs(b, B, 0);
for (auto a1 : A)
{
for (auto b1 : B)
{
if (check(a1.second, b1.second))
{
ans = min(ans, a1.first + b1.first);
}
}
}
if (ans == INT_MAX) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
在这个例子中，我们通过DFS找出了所有的可能操作，并将每一次操作的次数和字符串保存在一个vector中。然后遍历两个vector，判断当前的字符串是否相等，如果相等则更新最小操作次数。
注意：使用DFS可能会遇到超时的问题，因为DFS会穷尽所有可能的解空间。在实际应用中，可以基于DFS的思路进行剪枝或者使用其他算法如BFS、动态规划等。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
页:
[1]