蓝桥杯——车的放置 (C++)

题目来源：蓝桥杯算法训练

知识点：DFS搜索

问题描述
　　在一个n*n的棋盘中，每个格子中至多放置一个车，且要保证任何两个车都不能相互攻击，有多少中放法(车与车之间是没有差别的)
输入格式
　　包含一个正整数n
输出格式
　　一个整数，表示放置车的方法数
样例输入
2
样例输出
7
数据规模和约定
　　n<=8
　　【样例解释】一个车都不放为1种，放置一个车有4种，放置2个车有2种。

题目分析

类似 n皇后，这里每行、每列只能放一个车，对角线没有约束，所以一行行地放置就可以了。因为车之间没有区别，所以为了避免计算到重复的情况，每深入一层后，循环开始的位置都应该是上一层行数的下一行，即i + 1。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10;
int n, m;
int row[maxn], col[maxn];
int ans;

void DFS(int k, int h) {
	if(k == m) {
		ans++;
		return;
	}
	for(int i=h; i<n; i++) {
		if(row[i]) continue;
		row[i] = 1;
		for(int j=0; j<n; j++) {
			if(!col[j]) {
				col[j] = 1;
				DFS(k + 1, i + 1); //注意 i+1
				col[j] = 0;
			}
		}
		row[i] = 0;
	}	
}

int main() {
	cin >> n;
	ans = 0;
	
	for(m=0; m<=n; m++) {
		memset(row, 0, sizeof(int) * n);
		memset(col, 0, sizeof(int) * n);
		DFS(0, 0);
	}
	
	cout << ans << endl;
	
	return 0;
}