現(xiàn)有n種不同形狀的寶石，每種寶石有足夠多顆。欲將這些寶石排列成m行n列的一個(gè)矩陣，m<=n，使矩陣中每一行和每一列的寶石都沒有相同的形狀。試設(shè)計(jì)一個(gè)算法，計(jì)算出對于給定的m和n，有多少種不同的寶石排列方案。

分析：

寶石n種，又是n列，所以可以認(rèn)為保證每一行的寶石都不同（關(guān)鍵），判斷的時(shí)候只判斷列是否相同就行

#include<stdio.h>
#define n 3
#define m 3
int a[m][n];
int count=0;

bool OK(int x,int y){//因?yàn)橹耙呀?jīng)保證每一行都是不同的，所以O(shè)K方法只判斷列相不相同就行
    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){//到達(dá)最后一行 
                if(y==n-1){//到達(dá)最后一列 
                    count++;
                    return; 
                }else{
                    traceback(x,y+1);   
                }
            }else{//還沒有到達(dá)最后一行
                if(y==n-1){//到達(dá)某一行的最后一列 
                    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 ,保證每行內(nèi)寶石種類都不會重復(fù) 
        }
    }
    traceback(0,0); 
    printf("%d",count);
    return 0;
} 

運(yùn)行截圖