题目描述

另一边，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;
}