深度优先搜索

洛谷P1219

这是一道经典的深度优先搜索问题，深度优先搜索可用以下模板：

void dfs(int depth){
	if(达到边界）{
		记录解
	}
	for(枚举在depth这一深度，能够使用的解){
		if(解可行){
			记录解（记录已经被使用）
			dfs(depth+1)
			恢复解（恢复原状）
		}
	}
}

题目要求我们找到可行解，这个可行解，使得棋盘上的每一行，每一列，每一条对角线（一个位置有两条对角线）都只有一个棋子。

我们可以将行作为我们的dfs深度，在这一深度下即这一行，枚举每一列，枚举时需要增加判断，首先flag1是判断这一列没有被占领，然后是两条对角线flag2和flag3，不需要判断行的原因是，我们将行作为dfs深度，所以一行只会有一个棋子。

if(!flag1[i] && !flag2[depth+i] && !flag3[depth-i+20])

判断对角线的函数为行数和列数相加，以及行数和列数相减，因为在对角线上，函数为y = x + b或y = -x + b，所以以上面代码判断，加20的原因是可能有负数，比较两数是否相等，加上同一个数（20）不影响判断

根据上方提供模板可写出以下代码

#include<bits/stdc++.h>
using namespace std;
int path[15] = {0}, flag1[100], flag2[100], flag3[100], n, ans = 0;
void dfs(int depth) {
    if(depth > n) {
        ans++;
        if(ans <= 3) {
            for(int i = 1; i <= n; i++) cout << path[i] << ' ';
            cout << endl;
        }
        return;
    }
    for(int i = 1; i <= n; i++) {
        if(!flag1[i] && !flag2[depth+i] && !flag3[depth-i+20]) {
            path[depth] = i;
            flag1[i] = 1; flag2[depth+i] = 1; flag3[depth-i+20] = 1;
            dfs(depth+1);
            flag1[i] = 0; flag2[depth+i] = 0; flag3[depth-i+20] = 0;
        }
    }
}
int main() {
    cin >> n;
    dfs(1);
    cout << ans;
    system("pause");
}