当前位置:首页 > 搜索 > 深度优先搜索 > 正文
NOI2.5-323棋盘问题
3403+

题目大意:在一个n*n的棋盘上,某些格子可以放棋子,放的时候不能有两个棋子出现在同一行或者同一列,共有多少种摆放方案?

题目描述

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

输入

输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

输出

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1

解题思路

可以参考n皇后的思路,每一行选一列来放,或者该行直接不放,当放下k个棋子后,方案数+1。思路出来后,就是细节问题了,如不能放到棋盘外面,行还大于n就不要继续搜索。由于每次搜索,只会在棋盘范围内找#,所以多组数组也不需要赋初值,读入时会直接覆盖旧数据的。

当然,一行中有很多非空位“.”,且下一行也可能没有空位“#”,因此,我们还可以预先把空位放到一个数组里(队列),方便搜索的时候快速找到下一个空位在哪。这样,我们就不是一行一行放了,而是一个一个空位尝试放棋子,为了避免重复搜索,下一个棋子放的位置,不能放在前一个棋子的前面。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

NOI2.5-323棋盘问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!