dfs问题

lsmCC

#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；

FishC_GPT

在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[a]) return;    st[a] = 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[i], a[j]);            dfs(a, v, l + 1);            swap(a[i], a[j]); //恢复现场        }    }    v.pop_back();    st[a] = 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官方接口），如未能正确解答您的问题，请继续追问。