花3小时打上的注释，分享给大家。。
1 #include <cstdio> 2 #include <cstring> 3 const int MAXR = 20; 4 const int MAXC = 310; 5 const int MAXN = MAXR * MAXC + MAXC; 6 const int INF = MAXR * 10; 7 8 int n, m; 9 int L[MAXN], R[MAXN], U[MAXN], D[MAXN]; 10 int C[MAXN], O[MAXN], S[MAXN], H[MAXR]; 11 int nodeNumber; 12 13 void init() 14 { 15 for(int i=0;i<=m;++i) 16 { 17 L[i] = i - 1; 18 R[i] = i + 1; 19 U[i] = i; 20 D[i] = i; 21 C[i] = i; 22 O[i] = 0; 23 S[i] = 0; 24 } 25 L[0] = m; 26 R[m] = 0; 27 nodeNumber = m + 1; 28 memset(H, 0, sizeof(H)); 29 } 30 31 void insert(int i, int j) 32 { 33 if(H[i]) //判断这一行中有没有节点 34 { 35 L[nodeNumber] = L[H[i]]; //如果有节点了，就添加一个节点，并把左指针指向第一个节点的未被更新的左指针,也就是新节点的左指针 36 R[nodeNumber] = H[i]; //右指针指向该行第一个节点 37 L[R[nodeNumber]] = nodeNumber; //更新第一个节点的左指针 38 R[L[nodeNumber]] = nodeNumber; //更新前一个节点的右指针 39 } 40 else 41 { 42 L[nodeNumber] = nodeNumber; //如果没有节点就添加一个节点，并把左右指针指向自己 43 R[nodeNumber] = nodeNumber; 44 H[i] = nodeNumber; //标记为该行第一个节点 45 } 46 47 U[nodeNumber] = U[j]; //节点的上指针指向上面一个节点 48 D[nodeNumber] = j; //节点的下指针指向对应的列表头 49 U[D[nodeNumber]] = nodeNumber; //更新列表头的上指针指向当前节点 50 D[U[nodeNumber]] = nodeNumber; //更新上一个节点的下指针指向当前节点 51 52 C[nodeNumber] = j; //记录列号 53 O[nodeNumber] = i; //记录行号 54 55 ++ S[j]; //S当中记录着每列节点的个数 56 ++ nodeNumber; //新建一个节点 57 } 58 59 void remove(int c) 60 { 61 L[R[c]] = L[c]; //右节点的左指针指向原节点的左节点 62 R[L[c]] = R[c]; //左节点的右指针指向原节点的右节点 63 for(int i=D[c];i!=c;i=D[i]) //从该列往下第一个节点开始往下遍历 64 { 65 for(int j=R[i];j!=i;j=R[j]) //从当前行的第二个节点往右遍历，因为列已经被删除，所以第一个节点不用管 66 { 67 U[D[j]] = U[j]; //把前面删除的列上符合要求的行也删除 68 D[U[j]] = D[j]; 69 -- S[C[j]]; //把相应列上对应的节点数也减少1个 70 } 71 } 72 } 73 74 void resume(int c) 75 { 76 for(int i=U[c];i!=c;i=U[i]) //从该列最后一个节点往上遍历，不遍历列表头节点 77 { 78 for(int j=L[i];j!=i;j=L[j]) //从该行最后一个节点往左遍历，不遍历第一个节点 79 { 80 ++ S[C[j]]; //列上面恢复一个节点，节点数也+1 81 D[U[j]] = j; //恢复行 82 U[D[j]] = j; 83 } 84 } 85 R[L[c]] = c; //最后恢复列 86 L[R[c]] = c; 87 } 88 89 bool dfs(int k) 90 { 91 if(!R[0]) //如果列表头上第一个节点的右指针为0，即所有列都被删除，则搜索完成 92 { 93 return true; 94 } 95 //因为要输出最优秀（最少的行）的答案，每次都要优先搜索列节点最少的列 96 int count = INF, c; 97 for(int i=R[0];i;i=R[i]) //从第一个列开始，直到右指针指向列头，即逐列遍历 98 { 99 if(S[i] < count) //找到节点最少的列 100 { 101 count = S[i]; //count里面放最少的节点数 102 c = i; //把该列做标记 103 if(1 == count) //该列节点，为最少允许的情况直接算是找到了，跳出 104 { 105 break; 106 } 107 } 108 } 109 remove(c); //把该列和列上符合要求的行删除 110 for(int i=D[c];i!=c;i=D[i]) //在被删除的列上，往下遍历 111 { 112 for(int j=R[i];j!=i;j=R[j]) //对应的行上往右遍历 113 { 114 remove(C[j]); //如果行上有符合要求的列，删了 115 } 116 if(dfs(k+1)) //递归层数+1，深度搜索 117 { 118 return true; 119 } 120 for(int j=L[i];j!=i;j=L[j]) //从该行最后一个节点往左遍历，第一个节点不遍历 121 { 122 resume(C[j]); //恢复之前删除的*行* 123 } 124 } 125 resume(c); //递归跳出，恢复之前删除的列 126 return false; 127 } 128 129 int main() 130 { 131 int t; 132 while(~scanf("%d%d",&n,&m)) 133 { 134 init(); 135 /* 136 printf("L\tR\tU\tD\tC\tO\n"); 137 for(int i=0;i<=m;i++) 138 { 139 printf("%d\t",L[i]); 140 printf("%d\t",R[i]); 141 printf("%d\t",U[i]); 142 printf("%d\t",D[i]); 143 printf("%d\t",C[i]); 144 printf("%d\t\n",O[i]); 145 } 146 */ 147 for(int i=1;i<=n;++i) 148 { 149 for(int j=1;j<=m;++j) 150 { 151 scanf("%d", &t); 152 if(t) 153 { 154 insert(i, j); //建立抽象十字链表 155 } 156 } 157 } 158 bool flag = true; 159 for(int i=1;i<=m;++i) 160 { 161 if(S[i] == 0) //如果有一列没有一个节点，直接失败 162 { 163 flag = false; 164 break; 165 } 166 } 167 if(flag && dfs(0)) //进入深度搜索 168 { 169 printf("Yes, I found it\n"); 170 } 171 else 172 { 173 printf("It is impossible\n"); 174 } 175 } 176 return 0; 177 } 178 /* 179 6 7 180 0 0 1 0 1 1 0 181 1 0 0 1 0 0 1 182 0 1 1 0 0 1 0 183 1 0 0 1 0 0 0 184 0 1 0 0 0 0 1 185 0 0 0 1 1 0 1 186 */