这题一开始直接用暴力的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;
} |