蓝桥杯算法训练 车的放置 C++
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
在一个n*n的棋盘中,每个格子中至多放置一个车,且要保证任何两个车都不能相互攻击,有多少中放法(车与车之间是没有差别的)
输入格式
包含一个正整数n
输出格式
一个整数,表示放置车的方法数
样例输入
2
样例输出
7
数据规模和约定
n<=8
【样例解释】一个车都不放为1种,放置一个车有4种,放置2个车有2种。
#include<iostream>
using namespace std;
int N;
int ans=1; //刚开始什么也不放也属于一种答案
bool visited[10]; //标志被放置的列
void dfs(int step) //表示从第step行开始放
{
if(step>N) return ; //如果超过规定的棋盘边界N,跳出。
for(int i=1;i<=N;i++)
if(!visited[i]) //如果这一列没有被放置
{
visited[i]=true; //在这个位置放置它
ans++;
dfs(step+1); //不能在同一行放了,跳到下一行
visited[i]=false; //回溯
}
dfs(step+1); //不一定从第step行开始放(即第step行没有也可以),从step+1行开始放也可以
}
int main()
{
cin>>N;
dfs(1);//从第一行开始搜
cout<<ans;
return 0;
}