【2016.10.6NOIP普及模拟】Queen

发布于 2019-04-12  8 次阅读


题目描述

另一边,G也通过某种途径获得了另一张地图。好奇的G顺着地图走到了一间摆满石像的房子。
这时,最大的石像Alice开口说话了。她讲述了一个凄惨的故事,在此不作赘述。故事的结局就是,皇后家族被大Boss变成石像,镇守在这间屋子。要通过这间屋子,需要完成一项任务。
由于长期被困,皇后石像都变得非常好斗,她们不仅不希望自己所在的行和列不存在其它皇后石像,还不希望在自己附近的某个特定位置存在其它皇后石像。根据“人以类聚,物以群分”的原则,这个房间里的皇后石像不喜欢的特定位置是一致的,并且所有皇后不喜欢的特定位置都在她的右下方。
Alice负责调停皇后石像之间的纷争,寻找合适的摆放方法。又因为皇后石像不安于现状,如果长期呆在一个位置,会造成不堪设想的后果。所以Alice希望G在给定的时间T内摆放出所有合适的方案。因为这间房间年久失修,所以有些地方不能摆放石像。
G每摆放一种方案,至少需要1个单位时间。同时G又是个完美主义者,她希望每一种方案都能花尽量多的时间摆放到最好。G想知道,在每种方案花费时间相同的情况下,每种方案最多可以分配到的摆放时间(摆放时间都为整数)。

输入

第1行一个整数n(1≤n≤15),表示房间大小为n*n,同时表示有n个皇后石像。
第2行一个整数T,表示Alice给定的时间。
第3行两个整数,表示皇后石像不喜欢的位置。其中第一个数表示下方,第二个数表示右方。
第4行一个整数m,表示不能放石像的方格个数。
下面m行,每行两个整数,表示不能放石像的方格的位置。

输出

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

思路

深搜每一终方案,和普通的八皇后问题类似,只是加多一些判断条件和在最后进行判断

#include 
using namespace std;
long long x[20],f[20][20],a[20][20];
int n,m,xx,ans,yy,l,t;
int dfs(int dep)
{
    if (dep>n)
    {
        ans++;
        return 0;
    }
    for (int i=1;i<=n;i++)
        if (x[i]==0&&f[dep][i]!=1&&a[dep-xx][i-yy]!=1)
        {
            x[i]=1;
            a[dep][i]=1;
            dfs(dep+1);
            a[dep][i]=0;
            x[i]=0;
        }
}
int main()
{
    freopen("queen.in", "r", stdin);
   freopen("queen.out", "w", stdout);
    scanf("%d%d%d%d%d",&n,&t,&xx,&yy,&m);
    for (int i=1;i<=m;i++)
        {
            int hjy,yys;
            scanf("%d%d",&hjy,&yys);
            f[hjy][yys]=1;
        }

    dfs(1);
    if (ans==0||t/ans==0) 
    {
        printf("I cannot make it!\n");
        return 0;
    }

    if (t/ans<=t) printf("%d\n",t/ans);
      else printf("I cannot make it!\n");
    return 0;
}
]]>