HDU--2553 -- N皇后问题

本文主要是介绍HDU--2553 -- N皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5526    Accepted Submission(s): 2507

  
1
8
5
0

  
1
92
10

Code:

//一种坑爹答案而已

#include"stdio.h"
int main()
{
int a[11] = {1,0,0,2,10,4,40,92,352,724},n,i;
while(scanf("%d",&n),n && n<=10)
{
printf("%d\n",a[n-1]);
}
return 0;
}

下文另附完全版:

 超时版本:

//超时版本: 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int sum,x[11];
bool place(int k)
{
//int i;
//printf("k=%d\n",k);
//for(i=1;i<=n;i++) printf("%d ",x[i]);
//	printf("\n");
int j;
for(j=1;j<k;j++)
{
if(abs(j-k)==abs(x[j]-x[k]) || x[j]==x[k] ) return false; //在同一斜线或同一列	
}
return true;
}
void backtrack(int t,int n)
{
int i;
//	printf("t=%d,n=%d\n",t,n);
//	for(i=1;i<=n;i++) printf("%d ",x[i]);
//	printf("\n");
if(t>n) {
sum++;
//	printf("sum=%d\n",sum);
}
else
{
for(i=1;i<=n;i++)
{
x[t]=i;	
//	printf("%d\n",place(t,x));
if(place(t)) backtrack(t+1,n);
}
}
}
int main()
{
int n,i;	
while(scanf("%d",&n),n)
{	
sum = 0;
for(i=1;i<=n;i++) x[i]=0;
backtrack(1,n);
printf("%d\n",sum);
}
return 0;
}

 正确版本:

#include<iostream>
using namespace std;
#include"stdio.h"
#define MAX 12
int vst[MAX];               
int cnt[MAX];
int ans;
int n;
bool flag;		//vst[i]表示第i个皇后的列数,cnt[i]表示放i个皇后的可行方案个数
//ans存放的是当前方案个数,用于赋值给ans[i] ,n表示皇后个数的循环变量
//flag用来表示该位置能不能放皇后,能的话就为true 
void DFS(int row)     //深搜                
{
int i,j;
if(row==n+1)     //如果所放皇后个数大于要求个数n, 则该方案可行, ans+1
ans++;
else
for(i=1;i<=n;i++)	//该皇后之前的也需要进行循环,先选定一个位置看下面能放几个,如果不够,这个也要换 
{					//即首先确定一个位置,接着在剩余行放其余皇后,不行的话更换先确定的位置 
flag=true; 
vst[row]=i;  
for(j=1;j<row;j++) //将该皇后之前的各个皇后都与之进行比较,看是否满足条件 
{
if(vst[row]==vst[j]||vst[row]-row==vst[j]-j||vst[row]+row==vst[j]+j)      //关键 
{	//如果在同一斜线或者同一列就不能放 
flag=false;
break;    
}
}
if(flag)
DFS(row+1);	//如果能放,考虑放置下一个皇后 ,row+1 
}
}
int main()
{
int i;
for(n=1;n<11;n++)//从1~10先算出各个方案,下面直接输出~~ 
{
ans=0;
DFS(1);	//每次都是从1开始搜索 
cnt[n]=ans;
} 
while(~scanf("%d",&n),n)
{
printf("%d\n",cnt[n]);
}
return 0;
}

这篇关于HDU--2553 -- N皇后问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！