本文主要是介绍POJ 3074 SUKODU [Dancing Links DLX精准覆盖问题]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
DLX各种教程看完之后，马马虎虎会写了
真是有点抽象有点难，不过还是感谢各路大神完美的教程
QUES SOLVE：http://www.cnblogs.com/ylfdrib/archive/2010/10/06/1844559.html http://blog.csdn.net/liujiyong7/article/details/5934494
KNOWLEDGE PRE：http://blog.csdn.net/sunny606/article/details/7833551
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
int map[10][10];
char tmp[10][10];
int adj[800][340];
int ans[10][10];
int M,N;#define INF 0x3fffffff#define NN 330
#define MM 740
int cntc[NN];
int L[NN * MM], R[NN * MM], U[NN * MM], D[NN * MM], C[NN * MM];
int head;/*删除第c列*/
void remove(int c){L[R[c]] = L[c];R[L[c]] = R[c];int i, j;for (i = D[c]; i != c; i = D[i]){for (j = R[i]; j != i; j = R[j]){U[D[j]] = U[j];D[U[j]] = D[j];cntc[C[j]]--;}}
}
/*恢复第c列*/
void resume(int c){L[R[c]] = c;R[L[c]] = c;int i, j;for (i = D[c]; i != c; i = D[i]){for (j = R[i]; j != i; j = R[j]){U[D[j]] = j;D[U[j]] = j;cntc[C[j]]++;}}
}
int dfs(){if (R[head] == head) return 1;int min = INF;int c, i, j;for (i = R[head]; i != head; i = R[i]){if (cntc[i] < min){c = i;min = cntc[i];}}remove(c);for (i = D[c]; i != c; i = D[i]){//O[idx++] = (i - 1) / M;int r = (i - 1) / N;int num = (r + 8) / 9;int key = r % 9;if (key == 0) key = 9;int x = (num + 8) / 9;int y = num % 9;if (y == 0) y = 9;ans[x][y] = key;for (j = R[i]; j != i; j = R[j]){remove(C[j]);}if (dfs()) return 1;/*这个顺序很重要，删除和恢复的方向必须相反开始相同，都是向右的，结果TLE了*/for (j = L[i]; j != i; j = L[j]){resume(C[j]);}}resume(c);return 0;
}/*建图*/
int Build(){int i, j, now, pre, first;head = 0;for (j = head; j < N; j++){R[j] = j + 1;L[j + 1] = j; }L[head] = j;R[j] = head;/*列双向链表*/for (j = 1; j <= N; j++){pre = j;cntc[j] = 0;for (i = 1; i <= M; i++){if (adj[i][j]){now = i * N + j;C[now] = j;cntc[j]++;D[pre] = now;U[now] = pre;pre = now;}}now = j;D[pre] = now;U[now] = pre;if (cntc[j] == 0) return 0;}/*行双向链表*/for (i = 1; i <= M; i++){pre = first = -1;for (j = 1; j <= N; j++){if (adj[i][j]){now = i * N + j;if (pre != -1){R[pre] = now;L[now] = pre;}else{first = now;}pre = now;}}if (first != -1){now = first;R[pre] = now;L[now] = pre;}}return 1;
}int main()
{//freopen("/home/rainto96/in.txt","r",stdin);char tmpstr1[111],tmpstr[10][10];while(cin>>tmpstr1){ memset(adj,0,sizeof(adj));/*memset(map,0,sizeof(map));memset(tmp,0,sizeof(tmp));memset(ans,0,sizeof(ans));memset(L,0,sizeof(L));memset(R,0,sizeof(R));memset(U,0,sizeof(U));memset(D,0,sizeof(D));memset(C,0,sizeof(C));memset(cntc,0,sizeof(cntc));*/head=M=N=0;if(strcmp(tmpstr1,"end")==0) break;for(int i=0;i<81;i++)tmpstr[i/9+1][i%9+1]=tmpstr1[i];//#define DEBUG#ifdef DEBUGfor(int i=1;i<=9;i++){for(int j=1;j<=9;j++){cout<<tmpstr[i][j];}cout<<'\n';}#endiffor(int i=1;i<=9;i++){for(int j=1;j<=9;j++){map[i][j]=tmpstr[i][j]=='.'?0:(tmpstr[i][j]-'0');if(map[i][j]){int k=map[i][j];int t=9*(i-1)+j;adj[9*(t-1)+k][t]=1;adj[9*(t-1)+k][81+9*(i-1)+k]=1;adj[9*(t-1)+k][162+9*(j-1)+k]=1;adj[9*(t-1)+k][243+9*(3*((i-1)/3)+(j-1)/3)+k]=1;}else{for(int k=1;k<=9;k++){int t=9*(i-1)+j;adj[9*(t-1)+k][t]=1;adj[9*(t-1)+k][81+9*(i-1)+k]=1;adj[9*(t-1)+k][162+9*(j-1)+k]=1;adj[9*(t-1)+k][243+9*(3*((i-1)/3)+(j-1)/3)+k]=1;}}}}M=729;N=324;Build();dfs();for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)printf("%d",ans[i][j]);printf("\n");}return 0;
}
这篇关于POJ 3074 SUKODU [Dancing Links DLX精准覆盖问题]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
