POJ 3740 Easy Finding（舞蹈链）
/*舞蹈链模板题*/#include <cstdio>#include <cstring>const int mMax = 50, nMax = 500;int map[mMax][nMax];int M, N;struct Node{int left, right, up, down;int col;}node[mMax * nMax];//双向链表int len;int cnt[nMax];void init(int n){int i;for(i = 0; i <= n; ++ i){node[i].left = i - 1;node[i].right = i + 1;node[i].col = i;//node[i].down = i;node[i].up = i;}node[n].right = 0;node[0].left = n;}void remove(int c){int i, j;node[node[c].left].right = node[c].right;node[node[c].right].left = node[c].left;for(i = node[c].down; i != c; i = node[i].down){for(j = node[i].right; j != i; j = node[j].right)//因为每列只能包含一个1，所以可以把所有的列中对应的行全部删掉。//这里还有一个细节，因为前面执行过删除列操作，所以不需要对i再执行删除行操作，因为以后肯定不会再访问到{node[node[j].up].down = node[j].down;node[node[j].down].up = node[j].up;cnt[node[j].col] --;}}}void resume(int c)//先删除的后恢复{int i, j;for(i = node[c].up; i != c; i = node[i].up){for(j = node[i].left; j != i; j = node[j].left){node[node[j].up].down = j;node[node[j].down].up = j;cnt[node[j].col] ++;}}node[node[c].left].right = c;node[node[c].right].left = c;//先删除先恢复，也正确，但是有些情况会出现偏差，无法与原来状态对称/*int i, j;node[node[c].left].right = c;node[node[c].right].left = c;for(i = node[c].down; i != c; i = node[i].down){for(j = node[i].right; j != i; j = node[j].right){node[node[j].up].down = j;node[node[j].down].up = j;cnt[node[j].col] ++;}}*/}bool dfs(int k)//k表示已经找出了多少行{int i, j;if(node[N].right == N)//终止状态：列已经被全部删除。这里需要一个空节点，来进行判断return true;int c, _min = 0x7fffffff;for(i = node[N].right; i != N; i = node[i].right){if(cnt[i] < _min){_min = cnt[i];c = i;}}remove(c);for(i = node[c].down; i != c; i = node[i].down){//找到"一行"可能的解，然后递归for(j = node[i].right; j != i; j = node[j].right){remove(node[j].col);}if(dfs(k + 1)) return true;for(j = node[i].right; j != i; j = node[j].right){resume(node[j].col);}}resume(c);return false;}int main(){//freopen("e://data.in", "r", stdin);while(scanf("%d%d", &M, &N) != EOF){int i, j;init(N);int cur;memset(cnt, 0, sizeof(cnt));cur = N + 1;for(i = 0; i < M; ++ i){int start = cur;node[start].left = start;//初始化，为了形成环node[start].right = start;for(j = 0; j < N; ++ j){scanf("%d", &map[i][j]);if(map[i][j] == 1){node[cur].right = node[start].right;//这里需要四步操作，原来漏泄了③，一直WA。模拟双向链表的头部插入操作node[cur].left = start;node[node[start].right].left = cur;//③node[start].right = cur;node[cur].down = node[j].down;node[cur].up = j;node[node[j].down].up = cur;node[j].down = cur;node[cur].col = j;cur ++;cnt[j] ++;}}}if(dfs(0))printf("Yes, I found it\n");elseprintf("It is impossible\n");}return 0;}