蓝桥杯基础练习VIP-2n皇后问题-题解（C++代码）--dfs

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int vis[9][9];
int n,cou=0;
bool check(int x, int y, int c) //xy当前行列，c==2表示红皇后，c==3表示黑皇后
{
for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		if (vis[i][j] == c)
		{
			if (i == x || j == y || abs(i - x) == abs(j - y)) return false; //排除和之前放置的相同皇后同行同列同斜对线的情况
		}
	}
}
return vis[x][y] == 1;//如果当前欲放置位置与之前的不冲突，在判断此位置能否放
}
void dfs(int x, int c)
{
	if (x == n)
	{
		if (c == 3)cou++;
		else dfs(0, 3);//再深入，第二种皇后放置
		return;
	}
	for (int i = 0; i < n; i++)//当前行，每一列的情况
	{
		if (check(x, i, c))
		{
			int t = vis[x][i];
			vis[x][i] = c;
			dfs(x + 1, c);//深入
			vis[x][i] = t;//回溯
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin>>vis[i][j];
		}
	}
	dfs(0,2);
	cout << cou;
}