首页 > 代码库 > ZOJ - 1008 Gnome Tetravex
ZOJ - 1008 Gnome Tetravex
DFS题,类似八皇后问题,题目有点长,看了老半天才看懂。特别是上下左右数字要注意。还要注意剪枝,另外空行不能多输,输多了不能AC
(运行速度有点慢,能AC但1940ms,估计还有待优化)
1 #include<stdio.h> 2 #include<string.h> 3 const int maxn=25+5; 4 int num[maxn],curnum,vis[maxn],ok; 5 struct node{ 6 int top,bot,right,left; 7 bool operator==(const node &t) 8 { 9 return top==t.top && bot==t.bot && right==t.right && left==t.left;10 }11 }square[maxn],curque[maxn];12 void dfs(int cur,int n);13 int main()14 {15 int n,T=0,blank=0;16 while(scanf("%d",&n)==1 && n){17 memset(num,0,sizeof(num));18 memset(vis,0,sizeof(vis));19 curnum=0;20 T++;21 ok=0;22 for(int i=0;i<n*n;i++){23 int flag=1;24 scanf("%d%d%d%d",&square[i].top,&square[i].right,&square[i].bot,&square[i].left);25 for(int j=0;j<curnum;j++){26 if(square[i]==curque[j]){27 num[j]++;28 flag=0;29 break;30 }31 }32 if(flag){33 num[curnum]++;34 curque[curnum++]=square[i];35 }36 }37 dfs(0,n);38 if(blank)39 printf("\n");40 else41 blank=1;42 if(ok)43 printf("Game %d: Possible\n",T);44 else45 printf("Game %d: Impossible\n",T);46 47 }48 return 0;49 }50 void dfs(int cur,int n)51 {52 int xpos=cur%n;53 int ypos=cur/n;54 if(ok || cur==n*n){55 ok=1;56 return;57 }58 for(int i=0;i<curnum;i++){59 if(num[i]){60 if(xpos>0)61 if(square[cur-1].right!=curque[i].left)62 continue;63 if(ypos>0)64 if(square[cur-n].bot!=curque[i].top)65 continue;66 num[i]--;67 square[cur]=curque[i];68 dfs(cur+1,n);69 num[i]++;70 }71 }72 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。