发表随想

编程随想

会python真的可以为所欲为 by Python自学0(回) 396天前

这里还有人吗 by mikeKil1(回) 581天前

这里还有人吗 by mikeKil0(回) 581天前

每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。 by js特效0(回) 805天前

到处都是羊，不想上班 by Python自学0(回) 885天前

鸽子 by 张书娥0(回) 889天前

云代码 - c++代码库

排列宝石问题

2012-09-20 作者：神马举报

[c++]代码库

问题描述：
现有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;
}

网友评论 (发表评论)

暂无评论 (抢沙发)

发表评论：

评论须知：

1、评论每次加2分，每天上限为30；
2、请文明用语，共同创建干净的技术交流环境；
3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。

用户注册

用户登录