Problem Statement
给定一个矩形的棋盘，上面要么填"#"，要么填"."，问说能否找到一条路径，上面放着棋盘中所有的"#"，且相邻两个点的行编号和列编号间隔相等。
建立一个二分图，左边是行，右边是列，上面的"#"在二分图中表示为一条边，若两个点行编号相等，则这两个点在二分图中对应的边邻接于左部的点。因此所要求的路径对应与二分图中的交错的欧拉路径，这样完成了从哈密顿路到欧拉路的转换。
#include <iostream>#include <vector>#include <string>using namespace std;class MagicBoard{public:int mm[55][55], degR[55], degC[55];int s[55][55];void dfs(int i, int j) { s[i][j] = 1;for(int k = 0; k < 55; k++) {if(mm[i][k] && !s[i][k]) dfs(i, k);if(mm[k][j] && !s[k][j]) dfs(k, j); } }bool check() {// int s[55][55]; memset(s, 0, sizeof(s));int num = 0;for(int i = 0; i < 55; i++) {for(int j = 0; j < 55; j++) {if(mm[i][j] == 0) continue;if(s[i][j]) continue; dfs(i, j); num++; } } printf("num = %d\n", num);return num == 1 ? true : false; }string ableToUnlock(vector <string> b) { memset(mm, 0, sizeof(mm)); memset(degR, 0, sizeof(degR)); memset(degC, 0, sizeof(degC));int n = b.size();int m = b[0].length();for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(b[i][j] == '#') { mm[i][j] = 1; degR[i]++; degC[j]++; } } }if(!check()) return "NO";int res = 0, flag = 0;for(int i = 0; i < 55; i++) {if(degR[i] & 1) res++;if(degC[i] & 1) { res++; flag = 1; } } printf("%d %d\n", res, flag);if(!res || (res == 2 && flag)) return "YES";else return "NO"; }};转载于:https://www.cnblogs.com/litstrong/archive/2012/02/27/2369930.html
相关资源：数据结构—成绩单生成器