杭电 2553 N皇后问题

问题：

N皇后问题

Time Limit: 2000/1000 MS (java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 21548    Accepted Submission(s): 9644

PRoblem Description在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。你的任务是，对于给定的N，求出有多少种合法的放置方法。 

Input共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。 

Output共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。 

Sample Input

1850 
Sample Output
19210题解：1，逐行放置，则皇后不会横向攻击，因此只需检查是否纵向和斜向攻击即可，代码：
#include<cstdio>#include<string.h>int c[33],tot,n;void search(int cur){	int i,j;	if(cur==n)	tot++;	else for(i=0;i<n;i++)	{		int ok=1;		c[cur]=i;		for(j=0;j<cur;j++)		if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])		{			ok=0;			break;		}		if(ok)		search(cur+1);	}}int main(){	while(scanf("%d",&n)&&n)	{	tot=0;	memset(c,0,sizeof(c));    search(0);	printf("%d/n",tot);    }	return 0;}2：提高效率：利用二维数组vis[2][]直接判断当前尝试的皇后所在的列和两个对角线是否已有其他皇后。因为下标相减可能为负数，存取时要加上n.（对角线下标相加或相减相同）代码：
#include<cstdio>#include<string.h>int n,tot,vis[3][22],c[11];void search(int cur){	int i,j;	if(cur==n)	{	tot++;	return;}	else for(i=0;i<n;i++)	{		if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n])		//利用二维数组直接判断 		{			c[cur]=i;			vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;//修改全局变量 			search(cur+1);			vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0;//要恢复原状 		}	}}int main(){	while(scanf("%d",&n)&&n)	{		tot=0;		memset(c,0,sizeof(c));		memset(vis,0,sizeof(vis));		search(0);		printf("%d/n",tot);	}}但是以上代码对于这道题依然超时！！！借鉴了别人不超时的打表做法代码：
#include<stdio.h>#include<string.h>#include<stdlib.h>int n,ans;int map[15];int visit[15];   int sol[15];int dfs(int k){	int i,j,flag;	if(k==n+1)//  递归结束条件 	{		ans++;//做个说明，判断第一列开始，那么就是从第一列的第一行查找到第五行 		return 0;	}//此种方法是按照列来存储的，所以是从1-n来村的，就是说k是标志 	for(i=1;i<=n;i++)// 从第一行开始到第n行 	if(!visit[i])  //判断各行是否已经有棋子 	{		map[k]=i;//如果这一行没有棋子，则用map[k]=i来记录，其中i为第几行 		flag=1;// k为第几列，则皇后存储在第k列，第i行 		for(j=1;j<=k-1;j++) //判断是否在同一斜线上，j从第一列开始查找到第k-1列 		if((map[k]-map[j])==(k-j)||(map[k]-map[j])==(j-k))//画个图验证一下 		{			flag=0;			break;		}		if(flag)		{			visit[i]=1;			dfs(k+1);			visit[i]=0;  //释放第i列，进行下一次搜索，此处要注意递归到结束的时候会返回的 		}//一步步返回到某一步，再继续查找，这个递归只解释到这里吧 	}//自己举个9*9的例子就理解为什么了，或者6*6吧 }int main(){	int i;	for(i=1;i<=10;i++)//  先进行打表，就是先存储，要不然会超时 	{		ans=0;//  统计方法种数 		n=i;//   因为第16步要用到n，自己粘贴到dev上看看 		memset(map,0,sizeof(map));//初始化 		memset(visit,0,sizeof(visit));		dfs(1);//   1表示从第一列开始，可以自己花一个5*5的方格 		sol[i]=ans;	}	while(scanf("%d",&n),n)	printf("%d/n",sol[n]);	return 0;}