首页 > 代码库 > ZOJ - 1008 Gnome Tetravex

ZOJ - 1008 Gnome Tetravex

2024-07-12 15:16:55   220人阅读

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 }


联系
我们