这题一开始直接用暴力的DFS来做，果然到25的规模就挂了.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 |
vector<bool> visited(50, false);vector<vector<int> > vec_row(50);vector<vector<int> > vec_col(50);bool
findPath(vector<int> &x, vector<int> &y, int
idx, int
depth, int
direction) { if
(depth == x.size()) return
true; visited[idx] = true; if
(direction == 0) { int
row = x[idx]; for
(int
i = 0; i < vec_row[row].size(); i++) { if
(!visited[vec_row[row][i]]) { if
(findPath(x, y, vec_row[row][i], depth+1, 1)) return
true; } } } else
{ int
col = y[idx]; for
(int
i = 0; i < vec_col[col].size(); i++) { if
(!visited[vec_col[col][i]]) { if
(findPath(x, y, vec_col[col][i], depth+1, 0)) return
true; } } } visited[idx] = false; return
false;}//如果存在满足条件的遍历,返回true,否则返回falsebool
existPath(vector<int> &x, vector<int> &y) { int
k = x.size(); if
(k == 0) return
true; for
(int
i = 0; i < k; i++) { vec_row[x[i]].push_back(i); vec_col[y[i]].push_back(i); } for
(int
i = 0; i < k; i++) { if
(findPath(x, y, i, 1, 0) || findPath(x, y, i, 1, 1)) { return
true; } } return
false;} |
正确的做法是转化成欧拉回路：http://www.itint5.com/discuss/22/%E7%9B%B4%E8%A7%92%E8%B7%AF%E7%BA%BF%E9%81%8D%E5%8E%86%E6%A3%8B%E7%9B%98
这题可以直接转换为欧拉回路（路径）问题，这样，如果有解的时候要输出遍历路径的时候，也比较好办了。
具体的转换方式为：n,m的棋盘，建一个包含n+m个顶点的图G（为了方便说明，类似二分图将其分为两列，左边n个顶点，右边m个顶点，分别代表n行和n列）。对于目标格子(i,j)，左边第i个顶点和右边第j个顶点连一条边。最后的问题其实就是问转换之后的图G是否存在欧拉欧拉回路或者欧拉路径。
证明：相邻两步为直角，其实就是从某一行变到某一列。访问图G中的一条边，意味着访问棋盘中的一个目标点。由于图G中的边只连接左边的点（代表某一行）和右边的点（代表某一列），因此访问一条边就意味着从某一行变到了某一列，也就是转直角了。
所以问题变为能否从一点出发访问G中的所有边有且仅有一次。这个就是欧拉回路问题了。
所以欧拉路径是：1.连通；2.奇点为2，为0时是欧拉回路。
这里的连通我用并查集来做。注意写并查集的merge时，要先找到根，再merge。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 |
vector<int> djset;int
find(int
i) { int
x = i; while
(djset[x] != x) { x = djset[x]; } djset[i] = x; return
x;}void
merge(int
i, int
j) { djset[find(i)] = djset[find(j)];}//如果存在满足条件的遍历,返回true,否则返回falsebool
existPath(vector<int> &x, vector<int> &y) { vector<int> axis(100, 0); // 计算奇点数目 for
(int
i = 0; i < x.size(); i++) { axis[x[i]] = !axis[x[i]]; // 奇偶变换 } for
(int
i = 0; i < y.size(); i++) { axis[y[i]+50] = !axis[y[i]+50]; } int
count = 0; for
(int
i = 0; i < axis.size(); i++) { if
(axis[i]) count++; } if
(count != 0 && count != 2) return
false; djset.resize(x.size()); for
(int
i = 0; i < djset.size(); i++) { djset[i] = i; } // 判断连通性 for
(int
i = 0; i < x.size(); i++) { for
(int
j = i+1; j < x.size(); j++) { if
(x[i] == x[j]) { merge(i, j); } } } for
(int
i = 0; i < y.size(); i++) { for
(int
j = i+1; j < y.size(); j++) { if
(y[i] == y[j]) { merge(i, j); } } } for
(int
i = 0; i < x.size(); i++) { if
(find(i) != find(0)) { return
false; } } return
true;} |
原文：http://www.cnblogs.com/lautsie/p/3527523.html