种树(normal)

Time Limit:1000MS  Memory Limit:65536K

Total Submit:213 Accepted:114

Description

　　在6*6的方格地盘中，种植24颗树，使每行、每列都有4颗树。

　　求出所有可能的种植方案总数。

　　种植方案的说明：输出一个6*6的矩阵，种树的方格用“*”表示，没种树的用“.”表示。

　　如下是一种方案(（样例仅说明格式，并不代表结果)

****..

..****

**..**

..****

****..

**..**

　

Input

Output

一个数即总数

Sample Input

Sample Output

//以下表示其中的10种，不需要输出，输出总数即可Case 1:****..****..**..****..**..****..****Case 2:****..****..**..***.*.**.*.***..****Case 3:****..****..**..***.*.**..****.*.***Case 4:****..****..**..***..***.**.**..****Case 5:****..****..**..***..***..****.**.**Case 6:****..****..**..**.**.***..***..****Case 7:****..****..**..**.**.**..*****..***Case 8:****..****..**..**.*.****.*.**..****Case 9:****..****..**..**.*.***..*****.*.**Case 10:****..****..**..**..******..**..****

Source

elba

#include#includeusing namespace std;int s,l[7];void trees(int x,int k1,int k2){if (l[k1]>1 || l[k2]>1) return;//判断该列还可不可以插入空格if (x==6)//退出条件{s++;return; }l[k1]++;l[k2]++;//该列空格的数量加1for (int i=1;i<=5;i++) for (int j=i+1;j<=6;j++)   trees(x+1,i,j);l[k1]--;l[k2]--;//回溯}int main(){ for (int i=1;i<=5;i++) for (int j=i+1;j<=6;j++)   trees(1,i,j);cout<

题解：

本题有两种解法，第一种是一个一个格子决定种还是不种，可是这样时间会比较久，所以我就想到了用八皇后的做法，

for (int i=1;i<=5;i++)
  for (int j=i+1;j<=6;j++)
    trees(x+1,i,j);

首先一行的树要4颗，这样循环会比较麻烦，那么就可以循环空位的地方，x表示行数，i和j表示空位的位置。然后用变量L表示该列有多少个空位，最多2个。然后当列数到了6行之后就可以退出累加了。