dfs问题

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=1e9+10;
   
4. typedef long long ll;
   
5. #define INF 0x3f3f3f3f
   
6. #define x first
   
7. #define y second
   
8. // typedef pair<int,int>p;
   
9. int dx[]={-1,0,1,0},dy[]={0,-1,0,1}; //上左下右
   
10. // 使用dfs减枝
    
11. string a,b;
    
12. vector<pair<int,string>>A,B;
    
13. unordered_map<string ,bool >st;   //表示字符串的状态
    
14. void dfs(string a,vector<pair<int,string>>&v,int l) //表示从0开始
    
15. {
    
16.     st[a]=true;
    
17.     v.push_back({l,a});
    
18.     for(int i=0;i<a.length();i++)
    
19.     {
    
20.         string t=a.substr(0,i)+a.substr(i+1);
    
21.         if(st[t]||t=="")continue;
    
22.         dfs(t,v,l+1);
    
23. 
    
24.     }
    
25.    
    
26. }
    
27. bool check(string a,string b)
    
28. {
    
29.     int a1=stoi(a);
    
30.     int b1=stoi(b);
    
31.     if(a1%b1==0||b1%a1==0)return true;
    
32.     return false;
    
33. }
    
34. void solve()
    
35. {
    
36.     cin>>a>>b;
    
37.     dfs(a,A,0);
    
38.     st.clear();
    
39.     dfs(b,B,0);
    
40.     int ans=INF;
    
41.     for(auto a1:A)
    
42.     {
    
43.         for(auto b1:B)
    
44.         {
    
45.             if(check(a1.second,b1.second))
    
46.             {
    
47.                 ans=min(ans,a1.first+b1.first);
    
48.             }
    
49.         }
    
50.     }
    
51.     cout<<(ans==INF?-1:ans);
    
52.    
    
53.    
    
54.    
    
55.    
    
56. }
    
57. int main()
    
58. {
    
59.     int t;
    
60.     t=1;
    
61.     while(t--)
    
62.     {
    
63.         solve();
    
64.     }
    
65. }
    
66. //可以用二进制去做，但是不会，到时候再去补

复制代码

dfs函数是删除字符串的操作，不太懂，还有为什么要l+1；

FishC_GPT

在dfs问题中，使用DFS（深度优先搜索）可以遍历所有可能的解空间。但是在实际应用中，为了提高效率，我们需要进行剪枝操作。

下面是一个使用DFS减枝的例子，其中通过交换字符串中的两个字符，找出最小操作次数使得两个字符串相等。

1. #include <iostream>
2. #include <vector>
3. #include <unordered_map>
4. using namespace std;
6. unordered_map<string, bool> st; //表示字符串的状态
7. int ans = INT_MAX;
9. void dfs(string a, vector<pair<int, string>>& v, int l) //表示从0开始
10. {
11.     if (st[a]) return;
12.     st[a] = true;
13.     v.push_back({l, a});
14.     for (int i = 0; i < a.size(); i++)
15.     {
16.         for (int j = i + 1; j < a.size(); j++)
17.         {
18.             swap(a[i], a[j]);
19.             dfs(a, v, l + 1);
20.             swap(a[i], a[j]); //恢复现场
21.         }
22.     }
23.     v.pop_back();
24.     st[a] = false;
25. }
27. bool check(string a, string b)
28. {
29.     return a == b;
30. }
32. int main()
33. {
34.     string a, b;
35.     cin >> a >> b;
36.     vector<pair<int, string>> A, B;
37.     dfs(a, A, 0);
38.     st.clear();
39.     dfs(b, B, 0);
40.     for (auto a1 : A)
41.     {
42.         for (auto b1 : B)
43.         {
44.             if (check(a1.second, b1.second))
45.             {
46.                 ans = min(ans, a1.first + b1.first);
47.             }
48.         }
49.     }
50.     if (ans == INT_MAX) cout << -1 << endl;
51.     else cout << ans << endl;
52.     return 0;
53. }

复制代码

在这个例子中，我们通过DFS找出了所有的可能操作，并将每一次操作的次数和字符串保存在一个vector中。然后遍历两个vector，判断当前的字符串是否相等，如果相等则更新最小操作次数。

注意：使用DFS可能会遇到超时的问题，因为DFS会穷尽所有可能的解空间。在实际应用中，可以基于DFS的思路进行剪枝或者使用其他算法如BFS、动态规划等。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。