剛學的Dancing Link，也沒打算自己去寫一個十字鏈表的模板，就在網上找到了這個，嘿嘿，寫的真心不錯，以后有時間自己寫個模板。

轉載自：http://blog.csdn.net/lyhypacm/article/details/5923287

題意：

解決9*9的數獨問題。

思路：

Dancing Link，不會的可以看我轉的上一篇文章，講解很詳細，雖說Dancing Link不一定快，但是確實很好用。

代碼：

#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm>using namespace std;const int MAX=1000; const int oo=0x3f3f3f3f; const int nC=9*9*4; const int delta[]={1,82,163,244}; const int head=0;int cnt[MAX],st[MAX]; int left[MAX*MAX],right[MAX*MAX],up[MAX*MAX],down[MAX*MAX]; int row[MAX*MAX],col[MAX*MAX]; struct Ans {int r,c,k; }ans[MAX*MAX]; int M,K;void remove(const int& c) {left[right[c]]=left[c];right[left[c]]=right[c];for(int i=down[c];i!=c;i=down[i])for(int j=right[i];j!=i;j=right[j]){up[down[j]]=up[j];down[up[j]]=down[j];cnt[col[j]]--;} }void resume(const int& c) {for(int i=up[c];i!=c;i=up[i])for(int j=left[i];j!=i;j=left[j]){down[up[j]]=j;up[down[j]]=j;cnt[col[j]]++;}left[right[c]]=c;right[left[c]]=c; }bool dfs(const int& k) {if(right[head]==head){char s[100]={0};for(int i=0;i<k;i++)s[ans[st[i]].r*9+ans[st[i]].c]=ans[st[i]].k+'0';puts(s);return true;}int s=oo,c=0;for(int i=right[head];i!=head;i=right[i])if(cnt[i]<s){s=cnt[i];c=i;}remove(c);for(int i=down[c];i!=c;i=down[i]){st[k]=row[i];for(int j=right[i];j!=i;j=right[j])remove(col[j]);if(dfs(k+1))return true;for(int j=left[i];j!=i;j=left[j])resume(col[j]);}resume(c);return false; }void init() {left[head]=nC;right[head]=1;up[head]=down[head]=head;for(int i=1;i<=nC;i++){left[i]=i-1;right[i]=(i+1)%(nC+1);up[i]=down[i]=i;cnt[i]=0;col[i]=i;row[i]=0;}M=0;K=nC; }int makecolhead(const int& c) {K++;cnt[c]++;col[K]=c;row[K]=M;left[K]=right[K]=K;up[K]=c;down[K]=down[c];up[down[K]]=K;down[up[K]]=K;return K; }void addcol(const int& id,const int& c) {K++;cnt[c]++;col[K]=c;row[K]=M;left[K]=id;right[K]=right[id];left[right[K]]=K;right[left[K]]=K;up[K]=c;down[K]=down[c];up[down[K]]=K;down[up[K]]=K; }void addrow(const int& i,const int& j,const int& k) {int id;M++;ans[M].r=i;ans[M].c=j;ans[M].k=k+1;id=makecolhead(9*i+j+delta[0]);addcol(id,9*i+k+delta[1]);addcol(id,9*j+k+delta[2]);addcol(id,(i/3*3+j/3)*9+k+delta[3]); }int main() {char s[100];while(*gets(s)!='e'){init();for(int i=0;i<9;i++)for(int j=0;j<9;j++)if(s[i*9+j]=='.')for(int k=0;k<9;k++)addrow(i,j,k);elseaddrow(i,j,s[i*9+j]-'1');dfs(0);} return 0; }

總結

以上是生活随笔為你收集整理的poj3074(数独)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。