Friday, November 27, 2015

[itint5]直角路线遍历棋盘 - 阿牧遥 - 博客园

[itint5]直角路线遍历棋盘 - 阿牧遥 - 博客园
https://github.com/zdzapple/itint5/blob/master/%E7%9B%B4%E8%A7%92%E8%B7%AF%E7%BA%BF%E9%81%8D%E5%8E%86%E6%A3%8B%E7%9B%98.cpp

//如果存在满足条件的遍历,返回true,否则返回false
bool existPath(vector<int> &x, vector<int> &y)
{
int n = x.size();
if (x.empty())
return true;
int rowNum = x[0];
int colNum = y[0];
int i, j;
for (i = 0; i < n; ++  i)
{
if (rowNum < x[i])
rowNum = x[i];
if (colNum < y[i])
colNum = y[i];
}
// the graoh should be connected graph
//判断连通性
bool xa[50] = {false};
bool ya[50] = {false};
xa[x[0]] = true;
ya[y[0]] = true;
i = 1, j = x.size() - 1;
while (i <= j)
{
if(xa[x[i]] || ya[y[i]]) {
xa[x[i]] = true;
ya[y[i]] = true;
i ++;
j = x.size() - 1;
}
else {
int xt = x[j], yt = y[j];
x[j] = x[i];
y[j] = y[i];
x[i] = xt;
y[i]= yt;
j--;
}
}
if (i!=x.size())
return false;

// the number of odd degresses should be 0 or 2
vector<int> leftDegress(rowNum + 1, 0);
vector<int> rightDegress(colNum + 1, 0);
for (i = 0; i < n; ++ i)
{
leftDegress[x[i]] ++;
rightDegress[y[i]] ++;
}
int oddDegressCount = 0;
for (i = 0; i <= rowNum; ++ i)
{
if (leftDegress[i] % 2)
oddDegressCount ++;
}
for (i = 0; i <= colNum; ++ i)
{
if (rightDegress[i] % 2)
oddDegressCount ++;
}
return oddDegressCount == 0 || oddDegressCount == 2;
}

`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``;`
`}`

所以欧拉路径是：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``;`
`}`