poj3076(16*16数独)

转载自&＃xff1a;http://blog.csdn.net/lyhypacm/article/details/5923287

题意&＃xff1a;

一个16*16的数独问题。

思路&＃xff1a;

和poj3024一样&＃xff0c;就改点东西。

代码&＃xff1a;

#include
#include
#include
#include using namespace std;const int oo&＃61;0x3f3f3f3f;
const int nR&＃61;16*16*16&＃43;10;
const int nC&＃61;16*16*4;
const int MAX&＃61;nR*4&＃43;nC&＃43;10;
const int delta[]&＃61;{1,16*16&＃43;1,16*16*2&＃43;1,16*16*3&＃43;1};
const int head&＃61;0;int cnt[nC&＃43;10],st[nC&＃43;10];
int left[MAX],right[MAX],up[MAX],down[MAX];
int row[MAX],col[MAX];
struct Ans
{int r,c,k;
}ans[MAX];
int M,K;void remove(const int& c)
{left[right[c]]&＃61;left[c];right[left[c]]&＃61;right[c];for(int i&＃61;down[c];i!&＃61;c;i&＃61;down[i])for(int j&＃61;right[i];j!&＃61;i;j&＃61;right[j]){up[down[j]]&＃61;up[j];down[up[j]]&＃61;down[j];cnt[col[j]]--;}
}void resume(const int& c)
{for(int i&＃61;up[c];i!&＃61;c;i&＃61;up[i])for(int j&＃61;left[i];j!&＃61;i;j&＃61;left[j]){down[up[j]]&＃61;j;up[down[j]]&＃61;j;cnt[col[j]]&＃43;&＃43;;}left[right[c]]&＃61;c;right[left[c]]&＃61;c;
}bool dfs(const int& k)
{if(right[head]&＃61;&＃61;head){char s[300]&＃61;{0};for(int i&＃61;0;i}void init()
{left[head]&＃61;nC;right[head]&＃61;1;up[head]&＃61;down[head]&＃61;head;for(int i&＃61;1;i<&＃61;nC;i&＃43;&＃43;){left[i]&＃61;i-1;right[i]&＃61;(i&＃43;1)%(nC&＃43;1);up[i]&＃61;down[i]&＃61;i;cnt[i]&＃61;0;col[i]&＃61;i;row[i]&＃61;0;}M&＃61;0;K&＃61;nC;
}int makecolhead(const int& c)
{K&＃43;&＃43;;cnt[c]&＃43;&＃43;;col[K]&＃61;c;row[K]&＃61;M;left[K]&＃61;right[K]&＃61;K;up[K]&＃61;c;down[K]&＃61;down[c];up[down[K]]&＃61;K;down[up[K]]&＃61;K;return K;
}void addcol(const int& id,const int& c)
{K&＃43;&＃43;;cnt[c]&＃43;&＃43;;col[K]&＃61;c;row[K]&＃61;M;left[K]&＃61;id;right[K]&＃61;right[id];left[right[K]]&＃61;K;right[left[K]]&＃61;K;up[K]&＃61;c;down[K]&＃61;down[c];up[down[K]]&＃61;K;down[up[K]]&＃61;K;
}void addrow(const int& i,const int& j,const int& k)
{int id;M&＃43;&＃43;;ans[M].r&＃61;i;ans[M].c&＃61;j;ans[M].k&＃61;k;id&＃61;makecolhead(16*i&＃43;j&＃43;delta[0]);addcol(id,16*i&＃43;k&＃43;delta[1]);addcol(id,16*j&＃43;k&＃43;delta[2]);addcol(id,(i/4*4&＃43;j/4)*16&＃43;k&＃43;delta[3]);
}int main()
{char str[300];char s[300];int pos;bool blocks&＃61;false;while(~scanf("%s",str)){if(blocks)puts("");elseblocks&＃61;true;init();pos&＃61;0;for(int i&＃61;0;i<16;i&＃43;&＃43;)s[pos&＃43;&＃43;]&＃61;str[i];for(int i&＃61;1;i<16;i&＃43;&＃43;){scanf("%s",str);for(int j&＃61;0;j<16;j&＃43;&＃43;)s[pos&＃43;&＃43;]&＃61;str[j];}for(int i&＃61;0;i<16;i&＃43;&＃43;)for(int j&＃61;0;j<16;j&＃43;&＃43;)if(s[i*16&＃43;j]&＃61;&＃61;&＃39;-&＃39;)for(int k&＃61;0;k<16;k&＃43;&＃43;)addrow(i,j,k);elseaddrow(i,j,s[i*16&＃43;j]-&＃39;A&＃39;);dfs(0);}return 0;
}