这种横向纵向双管齐下的牛逼回溯法，让小弟我怎么是好？ 求神秘解答

这种横向纵向双管齐下的牛逼回溯法，让我如何是好？ 求大虾神秘解答。
Description 

现有n种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的一个矩阵，m≤n，使矩阵中每一行和每一列的宝石都没有相同形状。 
对于给定的m和n，计算出不同的宝石排列方案数。

Input 

第1行有2个正整数m和n，0＜m≤n＜9。 

Output 

将计算出的宝石排列方案数输出

Sample Input 


3 3

Sample Output 


12

Source 
Description 

现有n种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的一个矩阵，m≤n，使矩阵中每一行和每一列的宝石都没有相同形状。 
对于给定的m和n，计算出不同的宝石排列方案数。

Input 

第1行有2个正整数m和n，0＜m≤n＜9。 

Output 

将计算出的宝石排列方案数输出

Sample Input 


3 3

Sample Output 


12

Source 





正如算法实现里说的，这样做为了实现什么目的。

回溯的时候，在哪些部分实现的从左往右，从哪些部分实现的从上至下，是先深度还是先广度，swap()的作用比普通排列树
那种更难理解了，能讲得明白么，谢谢你们。



[解决办法]

探讨

这个似乎可以直接算，n种宝石的排列应该有n!种，以3个为例，共6种，123算一种，向前移1位231，再移312，这3种组成了1个环，共有2个环。每个环可以凑成一套矩阵，共c(n,m) * m!个。因此总共是：

(n!/n)(环的个数) * c(n,m) * m!（从环中选择) = (n-1)! * n!/(n-m)!m! * m! = (n-1)! * n! / (n-m)!

[解决办法]

探讨

12345
42513
25134

这是什么环？

[解决办法]
恩，看来n*n不能套用到n*m上，想错了，不好意思，希望没有误导大家。
不过这个问题有点像错排问题。大家可以从这个思路来算组合。

探讨

引用:
这个似乎可以直接算，n种宝石的排列应该有n!种，以3个为例，共6种，123算一种，向前移1位231，再移312，这3种组成了1个环，共有2个环。每个环可以凑成一套矩阵，共c(n,m) * m!个。因此总共是：

(n!/n)(环的个数) * c(n,m) * m!（从环中选择) = (n-1)! * n!/(n-m)!m! * m! = (n-1)!……

[解决办法]
非拉丁吧
[解决办法]
一，当m=n时，有人算过了
二，当m<n时，值t[m,n]=t[m,m]*t[(n-m),m]*C(m,n)组合数
然后递归吧

查看更多 下一篇