USACO1.5 Checker Challenge(checker)

本題は古典的なn皇后問題であり,遡及法を用いて解く.1回目のforサイクルで現在位置が前の皇后と衝突しているかどうかを検出した結果,最後の試験例で13を入力すると0.436 sタイムアウトし,その後2次元配列を用いて直接判断し,13を入力すると0.562秒しかかからず,空間交換時間の利用を学ぶ重要性を再び示した.
 

/*
ID:jzzlee1
PROG:checker
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
using namespace std;
ifstream fin("checker.in");
ofstream fout("checker.out");
int n,ans,k,c[15],vis[30][30];
void search(int cur)
{
	int i;
	if(cur==n)							//    ，      ，         
	{
		ans++;
		if(k<3)							//     
		{
			//cout<<c[0]+1;
			fout<<c[0]+1;
			for(int i=1;i!=n;i++)
				fout<<" "<<c[i]+1;
				//cout<<" "<<c[i]+1;
			fout<<endl;
			//cout<<endl;
			k++;
		}
	}
	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()
{
	//cin>>n;
	fin>>n;
	memset(c,0,sizeof(c));
	search(0);
	fout<<ans<<endl;
	//cout<<ans<<endl;
	return 0;
}