Another Eight Puzzle Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) Total Submission(s) : 12 Accepted Submission(s) : 4 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description Fill the following 8 circles with digits 1~8,with each number exactly once . Conntcted circles cannot be filled with two consecutive numbers.There are 17 pairs of connected cicles:A-B , A-C, A-DB-C, B-E, B-FC-D, C-E, C-F, C-GD-F, D-GE-F, E-HF-G, F-HG-H Filling G with 1 and D with 2 (or G with 2 and D with 1) is illegal since G and D are connected and 1 and 2 are consecutive .However ,filling A with 8 and B with 1 is legal since 8 and 1 are not consecutive .In this problems,some circles are already filled,your tast is to fill the remaining circles to obtain a solution (if possivle). Input The first line contains a single integer T(1≤T≤10),the number of test cases. Each test case is a single line containing 8 integers 0~8,the numbers in circle A~H.0 indicates an empty circle. Output For each test case ,print the case number and the solution in the same format as the input . if there is no solution ,print “No answer”.If there more than one solution,print “Not unique”. Sample Input 3 7 3 1 4 5 8 0 0 7 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Sample Output Case 1: 7 3 1 4 5 8 6 2 Case 2: Not unique Case 3: No answer Source 华东交通大学2008(秋季)ACM程序设计竞赛(公开赛) 没得什么讲的!就搜!死搜 #include<stdio.h>int mm[9][9]={0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,0, 0,1,0,1,0,0,0,0,0, 0,0,1,0,1,0,0,0,0, 0,0,0,1,0,1,0,0,0, 0,0,0,0,1,0,1,0,0, 0,0,0,0,0,1,0,1,0, 0,0,0,0,0,0,1,0,1, 0,0,0,0,0,0,0,1,0,};int f[9][9],mark[9],a[9],b[9];int N,doublemark;void dfs(int );int main(){ int t,i; f[0][0]=0; f[1][2]=f[2][1]=f[1][3]=f[3][1]=f[1][4]=f[4][1]=f[2][3]=f[3][2]=f[2][5]=f[5][2]=1; f[6][2]=f[2][6]=f[4][3]=f[3][4]=f[5][3]=f[3][5]=f[6][3]=f[3][6]=f[7][3]=f[3][7]=1; f[6][4]=f[4][6]=f[4][7]=f[7][4]=f[5][6]=f[6][5]=f[5][8]=f[8][5]=f[7][6]=f[6][7]=1; f[6][8]=f[8][6]=f[7][8]=f[8][7]=1; int T; scanf("%d",&T); t=1; while(t++<=T) { N=0; for(i=1;i<=8;i++) mark[i]=0; for(i=1;i<=8;i++) { scanf("%d",&a[i]); if(a[i]!=0) mark[a[i]]=1; if(a[i]==0) N++; } doublemark=0; dfs(N); printf("Case %d:",t-1); if(doublemark==1) { for(i=1;i<=8;i++) printf(" %d",b[i]); printf("\n"); } else if(doublemark>1) printf(" Not unique\n"); else printf(" No answer\n"); } return 0;} void dfs(int N){ int i,j,k,markg=1; if(N==0) { for(i=1;i<=8;i++) if(a[i]==0) return ; doublemark++; if(doublemark==1) for(i=1;i<=8;i++) b[i]=a[i]; return ; } int gg=0; for(i=1;i<=8&&gg==0;i++) { if(a[i]==0) { gg=1; for(j=1;j<=8;j++) { if(mark[j]==0) { markg=1; for(k=1;k<=8;k++) { if(k==i) continue; if(f[k][i]&&mm[a[k]][j]) {markg=0;break;} } // if(markg==0) return 0; if(markg==1) { a[i]=j; mark[j]=1; dfs(N-1); a[i]=0; mark[j]=0; } } } } } for(i=1;i<=8;i++) if(a[i]==0) return ; doublemark++; if(doublemark==1) for(i=1;i<=8;i++) b[i]=a[i]; return ;}
评论