百练 2754 八皇后

/*
著名的八皇后问题
DFS+回溯
由于每一行有且只有一个皇后
所以递归对每一行进行遍历即可
很多地方都不完善
稍后贴出改进版代码
*/
#define LOCAL
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int map[10][10],queen[100],nqueen=0;
bool legal(int x,int y)//判断当前位置是否可放
{
	int i,j;
	for(i=1;i<=8;i++)
	{
		if(i!=x&&map[i][y]==1)
			return false;
	}
	for(i=x,j=y;i>=1&&j>=1;i--,j--)
	{
		if(i!=x&&map[i][j]==1)
			return false;
	}
	for(i=x,j=y;i>=1&&j<=8;i--,j++)
	{
		if(i!=x&&map[i][j]==1)
			return false;
	}
	for(i=x,j=y;i<=8&&j>=1;i++,j--)
	{
		if(i!=x&&map[i][j]==1)
			return false;
	}
	for(i=x,j=y;i<=8&&j<=8;i++,j++)
	{
		if(i!=x&&map[i][j]==1)
			return false;
	}
	return true;
}
void getqueen()//存储得到的八皇后序列
{
	int sum=0,i,j,t=1;
	for(i=8;i>=1;i--)
	{
		j=1;
		while(map[i][j]!=1)
			j++;
		sum+=j*t;
		t*=10;
	}
	queen[nqueen++]=sum;
}
void DFS(int m)//深搜遍历m代表搜索深度也代表棋盘行数
{
	if(m>8) return;//放置完毕返回
	int i;
	for(i=1;i<=8;i++)//对第m行的各个格子进行遍历
	{
		if(!map[m][i]&&legal(m,i))//如果当前位置可放置一个皇后
		{
				map[m][i]=1;//标记为已放置
				DFS(m+1);//搜索下一行
				if(m==8)//如果八个皇后都已经放置完毕
					getqueen();//保存皇后序列
				map[m][i]=0;//反标记当前位置
		}
	}
}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif

		int ncase,n;
		memset(map,0,sizeof(map));
		DFS(1);//从第一行开始放置
		cin>>ncase;
		while(ncase--)
		{
			cin>>n;
			cout<<queen[n-1]<<endl;
		}
		return 0;
}