蓝桥杯——车的放置
问题描述
在一个n*n的棋盘中,每个格子中至多放置一个车,且要保证任何两个车都不能相互攻击,有多少中放法(车与车之间是没有差别的)
输入格式
包含一个正整数n
输出格式
一个整数,表示放置车的方法数
样例输入
2
样例输出
7
数据规模和约定
n<=8
【样例解释】一个车都不放为1种,放置一个车有4种,放置2个车有2种。
思路分析
直接用深搜解决最为简单,用一个变量表示行,因为车之间不能进行攻击,所以一行最多放一个车。用一个变量表示行,最多n行,然后用一维数组进行遍历做标记,一行最多摆放一个,然后记录摆放种数;最后输出结果即可;
#include <stdio.h>
int n;
int cont=1; //什么都不放也是一种
int a[100];
//深搜算法,用变量表示行,然后直接用一维数组表示各列进行遍历
int dfs(int stap)
{
int i;
if(stap>n)
return;
for(i=1;i<=n;i++) //判断这一列有没有放车
{
if(a[i]==0) //用1做标记,标记已经放了
{
a[i]=1;
cont++;
dfs(stap+1);
a[i]=0;
}
}
dfs(stap+1); //跳向下一行
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",cont);
return 0;
}