蓝桥杯——车的放置

问题描述

　　在一个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;
		
}