现有n种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的一个矩阵，m<=n，使矩阵中每一行和每一列的宝石都没有相同的形状。试设计一个算法，计算出对于给定的m和n，有多少种不同的宝石排列方案。
分析：
宝石n种，又是n列，所以可以认为保证每一行的宝石都不同（关键），判断的时候只判断列是否相同就行
#include<stdio.h>
#define n 3
#define m 3
int a[m][n];
int count=0;
bool OK(int x,int y){//因为之前已经保证每一行都是不同的，所以OK方法只判断列相不相同就行
for(int i=0;i<x;i++){
if(a[x][y]==a[i][y])
return false;
}
return true;
}
void traceback(int x,int y){
int temp;
for(int i=y;i<n;i++){
temp=a[x][y];
a[x][y]=a[x][i];
a[x][i]=temp;
if(OK(x,y)){
if(x==m-1){//到达最后一行
if(y==n-1){//到达最后一列
count++;
return;
}else{
traceback(x,y+1);
}
}else{//还没有到达最后一行
if(y==n-1){//到达某一行的最后一列
traceback(x+1,0);
}else{
traceback(x,y+1);
}
}
}
temp=a[x][y];
a[x][y]=a[x][i];
a[x][i]=temp;
}
}
int main(){
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
a[i][j]=j+1;//每一行都是1 2 3 ... n ,保证每行内宝石种类都不会重复
}
}
traceback(0,0);
printf("%d",count);
return 0;
}
运行截图
