本文主要是介绍hdu 2514 Another Eight Puzzle（DFS暴搜），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：
hdu 2514
题目大意：
任意两个连线相邻的数，不能连续。即abs(x-y)!=1
思路：
与数独题做法如出一辙。
用DFS暴搜所有情况，对结果进行检查。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10;
int num[MAXN];
bool vis[MAXN];
int anssum;//记录有多少种答案
int ansnum[MAXN];bool check()
{if(abs(num[1]-num[2])==1||abs(num[1]-num[3])==1||abs(num[1]-num[4])==1) return false;if(abs(num[2]-num[3])==1||abs(num[2]-num[5])==1||abs(num[2]-num[6])==1) return false;if(abs(num[3]-num[4])==1||abs(num[3]-num[5])==1||abs(num[3]-num[6])==1||abs(num[3]-num[7])==1) return false;if(abs(num[4]-num[6])==1||abs(num[4]-num[7])==1) return false;if(abs(num[5]-num[6])==1||abs(num[5]-num[8])==1) return false;if(abs(num[6]-num[7])==1||abs(num[6]-num[8])==1) return false;if(abs(num[7]-num[8])==1) return false;return true;
}bool DFS(int pos)
{if((pos==9&&check())||(pos==8&&num[8]!=0&&check()))//注意边界。1.当最后一空需要填时pos==9 2.当最后一个空已填好时pos==8{anssum++;if(anssum>1)//当答案大于1时，直接返回不用继续找了return true;memcpy(ansnum,num,sizeof(num));return false;}for(int i=pos;i<=8;i++){if(num[i]!=0)continue;for(int j=1;j<=8;j++){if(!vis[j]){vis[j]=true;num[i]=j;if(DFS(i+1)) return true;vis[j]=false;num[i]=0;}}if(num[i]==0)return false;}return false;
}
int main()
{int kase,T;scanf("%d",&T);for(int kase=1;kase<=T;kase++){memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));anssum=0;for(int i=1;i<=8;i++){scanf("%d",&num[i]);vis[num[i]]=true;}printf("Case %d:",kase);DFS(1);if(anssum==1)//根据答案的个数就可以输出了{for(int i=1;i<=8;i++)printf(" %d",ansnum[i]);printf("\n");}else{if(anssum==0)printf(" No answer\n");else printf(" Not unique\n");}}return 0;
}
这篇关于hdu 2514 Another Eight Puzzle（DFS暴搜）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
