最新消息:点击查看大S的省钱秘笈

POJ 1321 棋盘问题 C语言版

POJ题解 Slyar 81浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

2
1

Slyar:类似八皇后的一道题,DFS+回溯。每次标记当前棋子所在列为不可放,然后搜索下一行即可,回溯时将当前列恢复为可放置,可以省掉每次初始化标记数组。我是47MS过的,据说有人用什么"棋盘多项式"可以0MS过,不过我不会,嘎嘎...

转载请注明:Slyar Home » POJ 1321 棋盘问题 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. @Felix021, 像Djk、floyd、KMP等我现在都看不懂...悲剧... 能干嘛?=_=
    Slyar8年前 (2009-04-18)回复
  2. 开始刷POJ了,NB。 POJ我才过了几道题,界面太难看,不喜欢去。 不过今天为了项目的东东要回头看看KMP,头疼。 ------ p.s. 推荐一下中国移动的139信箱,免费的邮件推送服务阿,超赞~~
    Felix0218年前 (2009-04-18)回复