搜索
编程论坛
→
开发语言
→
『 C语言论坛 』
→ 竞赛题 《棋盘》
标题:
竞赛题 《棋盘》
只看楼主
天胖
等 级:
新手上路
帖 子:11
专家分:0
注 册:2008-10-8
楼主
问题点数:0 回复次数:3
竞赛题 《棋盘》
题目:
在N*N的方格盘中,若在某一个方格内方入一个黑子,那么与该方格相邻的上、下、左、右四个方格内不能再放白子(当然黑子的位置上也不能放白子)。
输入N,M.
要求输出N*N的棋盘用M个黑子覆盖有多少种使棋盘上无法放白子的方法。
若无解,输出0。
样例给了N=5,M=7,输出答案为22。
我自己想了半天,也只是用穷举,加上最最粗略的剪枝,数据稍大就招架不住了,不知道这类题目有没有较为成熟高效的方法?
谢谢!
搜索更多相关主题的帖子:
竞赛题
棋盘
2008-10-13 21:07
卧龙孔明
等 级:
贵宾
威 望:
59
帖 子:3872
专家分:684
注 册:2006-10-13
第
2
楼
得分:0
n,m的范围是多少?
如果不大,可以状态空间dp
My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-10-14 12:16
天胖
等 级:
新手上路
帖 子:11
专家分:0
注 册:2008-10-8
第
3
楼
得分:0
题目里没有给出n,m的范围。。。算是不太严谨的比赛,不过n,m不会太大
2008-10-14 19:54
simpley
等 级:
新手上路
帖 子:262
专家分:0
注 册:2005-2-23
第
4
楼
得分:0
当M,N有至少有一个为偶数时,M>=MN/2有解,解为(MN/2,M-MN/2)的组合.
当M,N有都为奇数时,M>=(MN-1)/2有解,解为((MN+1/2),M-(MN-1)/2)的组合.
编程中似乎奇偶不必分别编写,好象有函数直接可以得到需要的值。
(MN-1)/2可以用函数(MN/2)直接向下取整数值
(MN+1)/2可以用函数(MN/2)直接向上取整值
[[it] 本帖最后由 simpley 于 2008-10-14 21:47 编辑 [/it]]
myQQ::445750010
2008-10-14 21:37
4
1/1页
1
参与讨论请移步原网站贴子:
https://bbs.bccn.net/thread-238059-1-1.html
关于我们
|
广告合作
|
编程中国
|
清除Cookies
|
TOP
|
手机版
编程中国
版权所有,并保留所有权利。
Powered by
Discuz
, Processed in 0.359546 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved