CX漫游仙境(queen)

CX漫游仙境(queen)

测试数据来自 wjszez/1606

问题描述:
为了抵抗巫妖王的入侵,越来越多的JHOI国民加入了近卫军团以抵抗天灾军团的侵略。可是在东部战场,天灾军团的unlazy用他那破坏力极强的霜之哀伤打得近卫军团节节败退。在这危急关头,世界之树的下达了任务,要求JHOI的战士迅速找到剑圣在仙境留下的火之高兴,并会对寻找到神剑的战士进行试炼,让他成为新一代的剑圣以对抗死亡骑士unlazy。怀着对上一代剑圣由涅若的崇敬,CX踏上了去往仙境的路程……
  经过重重考验,CX终于找到了神剑,它就藏在一个屋子里!
  这时,屋子里最大的石像开口说话了。她讲述了一个凄惨的故事,在此不作赘述。故事的结局就是,皇后家族被大Boss变成石像,镇守在这间屋子。
  由于长期被困,皇后石像都变得非常好斗,她们不仅不希望自己所在的行和列不存在其它皇后石像,还不希望在自己附近的某个特定位置存在其它皇后石像。根据“人以类聚,物以群分”的原则,这个房间里的皇后石像不喜欢的特定位置是一致的,并且所有皇后不喜欢的特定位置都在她的右下方。
  最大的皇后负责调停皇后石像之间的纷争,寻找合适的摆放方法。又因为皇后石像不安于现状,如果长期呆在一个位置,会造成不堪设想的后果。所以最大的皇后希望CX在给定的时间T内摆放出所有合适的方案。因为这间房间年久失修,所以有些地方不能摆放石像。
CX每摆放一种方案,至少需要1个单位时间。同时CX又是个完美主义者,他希望每一种方案都能花尽量多的时间摆放到最好。CX想知道,在每种方案花费时间相同的情况下,每种方案最多可以分配到的摆放时间(摆放时间都为整数)。

输入格式:
第1行一个整数n(1≤n≤15),表示房间大小为n*n,同时表示有n个皇后石像。
第2行一个整数T,表示Alice给定的时间。
第3行两个整数,表示皇后石像不喜欢的位置。其中第一个数表示下方,第二个数表示右方。(即MAP[i+x,j+y]不可以有皇后)
第4行一个整数m,表示不能放石像的方格个数。
下面m行,每行两个整数,表示不能放石像的方格的位置。

输出格式:
一个整数,每种方案表示最多可以分配到的摆放时间。
如果不能再规定时间T内完成,则输出“I cannot make it!”

样例输入:
5
50
2 1
5
1 4
2 2
3 3
4 1
5 5

样例输出:
1

样例解释:
此样例共有26种摆放方案。

信息

ID
2018
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者