西安交大 软件53 蔡少斐
题号：5_10
题目叙述：
现有n种不同形状的宝石，每种n颗，共n*n颗。同一形状的n颗宝石分别具有n种不同的颜色c1,c2,…,cn中的一种颜色。欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同的形状和n种不同颜色。是设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。
输入数据：
只有一个整数n
输出数据：
一个整数，代表不同的宝石排列方案。
题目解答：
问题将采用回溯法解决，首先搜索其所有的解空间，并生成解空间树，将满足条件的情况记录下来。
由于要求每一行宝石的形状和颜色均不相同，因此我们可以从行开始，生成行的有效全排列，然后对刚生的位置进行列有效判定，如果成功则继续向下搜索，不成功则重新生成排列，继续判定。
实现细节：在行进行生成2个排列的时候，先生成形状的排列，然后对形状进行列有效判定，若成功则进一步生成行颜色排列，并对颜色进行列有效判定。若都成功，那么这一颗石子也就确定了，则检验该石子是否在以前出现过，若出现过则放置失败，继续进行同级搜索，否则的话，我们就该考虑向下一个位置的搜索了。
下一个位置的确定有3种情况，第一种是如果当前位置为(n,n)那么不继续进行搜索，而是Ans++。第二种情况是如果当前位置为(x,n)那么下一个搜索的位置就是(x+1,1)。
另外，在进行列有效判定时，采用了std::set数据结构进行辅助设计,可以加速判定。
代码实现：
#include
#include
#include
#include
usingnamespace std; int used[10][10]; int shapes[10][10]; int colors[10][10]; set
col_c[10]; set
col_s[10]; int n; int cnt = 0; int dfs(int x, int y ) { int f = 0; for ( int i = y; i <= n; i++ ) { swap( shapes[x][i], shapes[x][y]); if ( col_s[y].count( shapes[x][y]) == 0 ) { col_s[y].insert(shapes[x][y] ); for ( int j = y; j <= n;j++ ) { swap( colors[x][j],colors[x][y] ); if ( col_c[y].count(colors[x][y] ) == 0 ) { col_c[y].insert(colors[x][y] ); if (!used[shapes[x][y]][colors[x][y]] ) { used[shapes[x][y]][colors[x][y]] = 1; f = 1; if ( x== n && y == n ) { ++cnt; }else { if( y == n ) { dfs(x + 1, 1 ); }else { dfs(x, y + 1 ); } } used[shapes[x][y]][colors[x][y]]= 0; } col_c[y].erase(colors[x][y] ); } swap( colors[x][j],colors[x][y] ); } col_s[y].erase(shapes[x][y] ); } swap( shapes[x][i], shapes[x][y]); } return(f); } int main() { cin >> n; for ( int x = 1; x <= 9; x++ ) for ( int i = 1; i <= 9; i++ ) { shapes[x][i] = colors[x][i]= i; } dfs( 1, 1 ); cout << "答案:" << cnt<< endl; return(0); }
运行结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/226451.html原文链接：https://javaforall.net
