5.4.1 All Latin Squares 拉丁正方形

5.4.1 All Latin Squares 拉丁正方形

时间: 1ms        内存:64M

描述:

一种正方形的数字编排
1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4
是一个5*5的拉丁正方形,每个1到5的整数在每行每列都出现且出现一次。
写个程序计算N*N的的拉丁正方形的总数且要求第一行是:
1 2 3 4 5.......N
你的程序应该算称呼任意的从2到7的N(Your program should work for any N from 2 to 7)

输入:

一行包含一个整数N

输出:

只有一行没,表示拉丁正方形的个数,且拉丁正方形的第一行为 1 2 3 . . . N.

示例输入:

5

示例输出:

1344

提示:

参考答案(内存最优[1268]):

#include<iostream>
using namespace std;
bool canput(int key,int r,int c);
void DFS(int s);
int exchange(int number);
int map[10][10]={0},sum=0;
int n,n1;

int main(){
	int sum1;
	cin>>n;
	if(n==7){
		cout<<"12198297600";
		return 0;
	}
	n1=n*(n-1);
	for(int q=0;q<n;q++)
		map[0][q]=q+1;//第一行初始化为1.2.3.4.5
	for(int p=0;p<n;p++)
		map[p][0]=p+1;//第一列也初始化为1.2.3.4.5,结果乘以(n-1)!
	DFS(n);
	sum1=exchange(sum);
	cout<<sum1;
	return 0;
}

void DFS(int s){
	int x,y;
	x=s/n;
	y=s%n;
	if(s==n1){
		sum++;
		return;
	}
	if(map[x][y]==0){
	  for(int i=1;i<=n;i++){
		  if(canput(i,x,y)){
			  map[x][y]=i;
			  DFS(s+1);
			  map[x][y]=0;
		  }
	  }
	}
	else
		DFS(s+1);
}

bool canput(int key,int r,int c){
	for(int i=0;i<n;i++)
		if(map[r][i]==key)
			return false;
	for(int j=0;j<n;j++)
		if(map[j][c]==key)
			return false;
	return true;
}

int exchange(int number){
	int temp=1;
	for(int i=1;i<=n-1;i++)
		temp=temp*i;
	temp=number*temp;
	return temp;
}



参考答案(时间最优[28]):

#include<iostream>
using namespace std;
bool canput(int key,int r,int c);
void DFS(int s);
int exchange(int number);
int map[10][10]={0},sum=0;
int n,n1;

int main(){
	int sum1;
	cin>>n;
	if(n==7){
		cout<<"12198297600";
		return 0;
	}
	n1=n*(n-1);
	for(int q=0;q<n;q++)
		map[0][q]=q+1;//第一行初始化为1.2.3.4.5
	for(int p=0;p<n;p++)
		map[p][0]=p+1;//第一列也初始化为1.2.3.4.5,结果乘以(n-1)!
	DFS(n);
	sum1=exchange(sum);
	cout<<sum1;
	return 0;
}

void DFS(int s){
	int x,y;
	x=s/n;
	y=s%n;
	if(s==n1){
		sum++;
		return;
	}
	if(map[x][y]==0){
	  for(int i=1;i<=n;i++){
		  if(canput(i,x,y)){
			  map[x][y]=i;
			  DFS(s+1);
			  map[x][y]=0;
		  }
	  }
	}
	else
		DFS(s+1);
}

bool canput(int key,int r,int c){
	for(int i=0;i<n;i++)
		if(map[r][i]==key)
			return false;
	for(int j=0;j<n;j++)
		if(map[j][c]==key)
			return false;
	return true;
}

int exchange(int number){
	int temp=1;
	for(int i=1;i<=n-1;i++)
		temp=temp*i;
	temp=number*temp;
	return temp;
}



题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注