这题一开始直接用暴力的DFS来做，果然到25的规模就挂了.
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,否则返回false
bool 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。
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,否则返回false
bool 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;
}