排列宝石问题

问题描述：
现有n种不同形状的宝石，每种n颗，共n*n颗。同一种形状的n颗宝石分别具有n种不同的颜色c1, c2, ...,cn中的一种颜色。欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。

Input
每组测试数据为1个正整数n，0<n<5。

Output
输出宝石排列方案数

Sample Input
1
2

Sample Output
1
0

#include<iostream>
#include<algorithm>
using namespace std;
const int len=10;
int a[len][len];
int b[len][len];
int cc[len][len];
int dd[len][len];
int ee[len][len];
int n,cnt;
void init()
{
	for ( int i=1; i<=n; i++ )
	{
		for ( int j=1; j<=n; j++ )
		{
			a[i][j]=j;
			b[i][j]=j;
			cc[i][j]=0;
		}
	}
}
int ok ( int r,int c,int k,int fla )
{
	if ( fla )
	{
		if ( cc[a[r][c]][b[r][k]] ) return 0;
		for ( int i=1; i<r; i++ )
		{
			if ( b[i][c]==b[r][k] )
				return 0;
		}
	}
	else
	{
		for ( int i=1; i<r; i++ )
		{
			if ( a[i][c]==a[r][k] )
				return 0;
		}
	}
	return 1;
}
void backtrack ( int r,int c )
{
	for ( int i=c; i<=n; i++ )
	{
		if ( ok ( r,c,i,0 ) )
		{
			swap ( a[r][c],a[r][i] );
			for ( int j=c; j<=n; j++ )
			{
				if ( ok ( r,c,j,1 ) )
				{
					swap ( b[r][c],b[r][j] );
					cc[a[r][c]][b[r][c]]=1;
					if ( c==n )
					{
						if ( r==n )
						{
							cnt++;
						}
						else backtrack ( r+1,1 );
					}
					else backtrack ( r,c+1 );
					cc[a[r][c]][b[r][c]]=0;
					swap ( b[r][c],b[r][j] );
				}
			}
			swap ( a[r][c],a[r][i] );
		}
	}
}
int main()
{
	while ( cin>>n )
	{
		cnt=0;
		init();
		backtrack ( 1,1 );
		cout<<cnt<<endl;
	}
	return 0;
}