[ CodeVS冲杯之路 ] P1295

　　不充钱，你怎么AC？

　　题目：http://codevs.cn/problem/1295/

　　数据很小，直接DFS，加上剪枝

　　剪枝其实就是判重，首先深度是行下标，这里自带不重复，枚举的列下标，用 f 记录每一列是否用过

　　斜着的用下标相加减控制，如下图

　　x 为横坐标，y 为纵坐标

　　对于每根红线，x+y 相等

　　对于每根蓝线，n-x-y 相等

　　我们就用 g 表示一条红线是否用过，y 表示一条蓝线是否用过

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N=;

 int ans,n;

 bool f[N],g[N],y[N];

 void dfs(int x)

 {

   if (x>n)

     {

       ans++;

       return;

     }

   int i;

   for (i=;i<=n;i++)

     {

       if (f[i]||g[x+i]||y[n-x+i]) continue;

       f[i]=;

       g[x+i]=;

       y[n-x+i]=;

       dfs(x+);

       f[i]=;

       g[x+i]=;

       y[n-x+i]=;

     }

 }

 int main()

 {

   scanf("%d",&n);

   dfs();

   printf("%d",ans);

   return ;

 }

巴特西

[ CodeVS冲杯之路 ] P1295

最新文章

热门文章