八皇后
2025-01-20 19:42:51
发布于：上海
16阅读
0回复
0点赞
#include<iostream>
using namespace std;
const int N = 5e5 + 5;
int vis[N];//vis[now]=i 表示第now行放在了第i列
int n = 8;
// 确定能不能放在 x,y 这个位置
bool judge(int x, int y)
{
for (int i = 1; i <= x - 1; i++) {//判断列
if (vis[i] == 0) continue; //第i行还没放置皇后，不用判断
if (vis[i] == y)return false;
}
for (int i = 1; i <= x - 1; i++) {//左对角线（逆时针）
if (vis[i] == 0) continue;
if (x - i == y - vis[i])return false;
}
for (int i = 1; i <= x - 1; i++) {//右对角线（顺时针）
if (vis[i] == 0) continue;
if (x + y == i + vis[i])return false;
}
return true;
}
int cnt;//方案数
void check() {
cnt++;
}
void dfs(int now)
{
if (now == n + 1)
{
check();
return;
}
if (vis[now] != 0) {//这一行中已经放置了皇后
if (!judge(now, vis[now])) return; //如果放置的位置不合法，结束
dfs(now + 1);//否则直接枚举下一行
return;
}
for (int i = 1; i <= n; i++)//枚举列
{
if (judge(now, i))//如果可以放在这
{
vis[now] = i;//第now行放在第i列
dfs(now + 1);
vis[now] = 0;
}
}
}
int main()
{
char a;
for (int i = 1; i <= n; i++) {
bool flag = 0;//判断这一行中是否放置了皇后
for (int j = 1; j <= n; j++) {
cin >> a;
if (a == 'Q') {
if (flag == 1) {//同一行中放置了多个皇后
cout << "0";
return 0;//一定没有合法方案
}
if (!judge(i, j)) {//如果放置的位置不合法
cout << "0";//一定没有合法方案
return 0;
}
flag = 1;
vis[i] = j;
}
}
}
dfs(1);
cout << cnt;
return 0;
}
这里空空如也
有帮助，赞一个