算法问题实战策略 PICNIC

下面是另一道搜索题目的解答过程
题目是《算法问题实战策略》中的一题
oj地址是韩国网站连接比较慢 https://algospot.com/judge/problem/read/PICNIC
大意如下

输入
3 
2 1 
0 1 
4 6 
0 1 1 2 2 3 3 0 0 2 1 3 
6 10 
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

输出
1
3
4

也是上来就撸一把DFS
全部能够匹配完成则计数增加1
但是有很多重复计算
我试过记录关系对的时候以数值大小为序只能排除一部分重复计算
错误的代码:

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 
 6 using namespace std;
 7 
 8 /*
 9 3
10 2 1
11 0 1
12 4 6
13 0 1 1 2 2 3 3 0 0 2 1 3
14 6 10
15 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
16 //====================================
17 1
18 3
19 4
20 */
21 
22 int t;
23 int a, b;
24 int n, m;
25 typedef pair<int, int> PII;
26 
27 
28 bool isFriend(int i, int j, const vector<PII>& friendv)
29 {
30     int minIdx = min(i, j);
31     int maxIdx = max(i, j);
32 
33     for (auto& e : friendv) {
34         if (e.first == minIdx && e.second == maxIdx)
35             return true;
36     }
37 
38     return false;
39 }
40 
41 
42 int dfs(bool isChecked[],const vector<PII>& friendv)
43 {
44     int firstFree = -1;
45     for (int i = 0; i < n; i++) {
46         if (isChecked[i] == false){
47             firstFree = i;
48             break;
49         }
50     }
51 
52     if (-1 == firstFree)
53         return 1;
54 
55     int ret = 0;
56 
57 
58     for (int secondFree = firstFree + 1; secondFree < n; secondFree++) {
59         if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false 
60                 && isFriend(firstFree, secondFree, friendv)) {
61             isChecked[firstFree] = true; isChecked[secondFree] = true;
62             ret += dfs(isChecked, friendv);
63             isChecked[firstFree] = false; isChecked[secondFree] = false;
64         }
65     }
66 
67 
68     return ret;
69 }
70 
71 
72 
73 
74 int main()
75 {
76     cin >> t;
77 
78     while (t--) {
79         cin >> n >> m;
80         vector<PII> friendv;
81         bool isChecked[160] = {false};
82         while (m--) {
83             cin >> a >> b;
84             friendv.push_back({min(a,b),max(a,b)});
85         }
86         sort(friendv.begin(), friendv.end());
87         cout << dfs(isChecked, friendv);
88     }
89 
90 
91     return 0;
92 }

View Code

经过调试发现DFS中双重循环有很大问题
i=0时候检测出 0 1配对然后检测出2 3 配对.
但是当i=2时也能检测2 3 配对以及 0 1 配对。

于是做了以下修改，解决重复问题
ac代码

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 
 6 using namespace std;
 7 
 8 /*
 9 3
10 2 1
11 0 1
12 4 6
13 0 1 1 2 2 3 3 0 0 2 1 3
14 6 10
15 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
16 //====================================
17 1
18 3
19 4
20 */
21 
22 int t;
23 int a, b;
24 int n, m;
25 typedef pair<int, int> PII;
26 
27 
28 bool isFriend(int i, int j, const vector<PII>& friendv)
29 {
30     int minIdx = min(i, j);
31     int maxIdx = max(i, j);
32 
33     for (auto& e : friendv) {
34         if (e.first == minIdx && e.second == maxIdx)
35             return true;
36     }
37 
38     return false;
39 }
40 
41 
42 int dfs(bool isChecked[],const vector<PII>& friendv)
43 {
44     int firstFree = -1;
45     for (int i = 0; i < n; i++) {
46         if (isChecked[i] == false){
47             firstFree = i;
48             break;
49         }
50     }
51 
52     if (-1 == firstFree)
53         return 1;
54 
55     int ret = 0;
56 
57 
58     for (int secondFree = firstFree + 1; secondFree < n; secondFree++) {
59         if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false 
60                 && isFriend(firstFree, secondFree, friendv)) {
61             isChecked[firstFree] = true; isChecked[secondFree] = true;
62             ret += dfs(isChecked, friendv);
63             isChecked[firstFree] = false; isChecked[secondFree] = false;
64         }
65     }
66 
67 
68     return ret;
69 }
70 
71 
72 
73 
74 int main()
75 {
76     cin >> t;
77 
78     while (t--) {
79         cin >> n >> m;
80         vector<PII> friendv;
81         bool isChecked[160] = {false};
82         while (m--) {
83             cin >> a >> b;
84             friendv.push_back({min(a,b),max(a,b)});
85         }
86         sort(friendv.begin(), friendv.end());
87         cout << dfs(isChecked, friendv)<<endl;
88     }
89 
90 
91     return 0;
92 }

View Code

作者: itdef
欢迎转帖请保持文本完整并注明出处
技术博客 http://www.cnblogs.com/itdef/
B站算法视频题解
https://space.bilibili.com/18508846
qq 151435887
gitee https://gitee.com/def/
欢迎c c++ 算法爱好者 windows驱动爱好者服务器程序员沟通交流
如果觉得不错，欢迎点赞，你的鼓励就是我的动力
阿里打赏