试题 算法训练 车的放置（蓝桥杯c++）

问题描述
　　在一个n*n的棋盘中，每个格子中至多放置一个车，且要保证任何两个车都不能相互攻击，有多少中放法(车与车之间是没有差别的)
输入格式
　　包含一个正整数n
输出格式
　　一个整数，表示放置车的方法数
样例输入
2
样例输出
7
数据规模和约定
　　n<=8
　　【样例解释】一个车都不放为1种，放置一个车有4种，放置2个车有2种。
算法思路：
这道题考察的是搜索回溯算法，我们都知道在象棋里车的攻击方式是直线行的，也就是说，只要不把他们放在同一行或者同一列就可以避免相互攻击，从题中我们可以了解到，题目要求不一定在每一行都必须放，即在这一行放不放都是一种方案（这就是与n皇后问题不同的地方）。因此我们搜索的时候都会对应两种选择，在这一行放或者不在这一行放，每种选择都要搜索一遍。

#include  <bits/stdc++.h>
using namespace std;
int N;
long long 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++; //该情况的答案+1
            dfs(step+1); //肯定不能在同一行放了，跳到下一行
            visited[i]=false; //回溯
        }
    dfs(step+1); //不一定从第step行开始放（即第step行没有也可以），从step+1行开始放也可以
}
int main()
{
    cin>>N;
    dfs(1);//从第一行开始搜
    cout<<ans;
    return 0;
}

下面我根据搜索的步骤给大家画一下搜到的答案的顺序情况
1.什么也不放

2.放第1行第1列

3.在2的基础上放第2列

4.回溯，放在第1行第2列

5.在4的基础上放第2行

6.回溯，第1行什么也不放，从第2行第1列开始放

7.回溯，从第2行第2列开始