题目
题目链接
题解
DFS。
八皇后问题改编而已,加入判断左上三格内和右上三格内是否存在皇后。
代码
#include<bits/stdc++.h>
using namespace std;
int n, ans;
int col[15], vis[15][15];
bool check (int x, int y) {
int tx = x, ty = y, cnt = 0;
while (tx >= 0 && ty >= 0 && cnt < 3) { // 左上
if (vis[tx][ty]) return false;
tx --, ty --, cnt ++;
}
tx = x, ty = y, cnt = 0;
while (tx >= 0 && ty < n && cnt < 3) { // 右上
if (vis[tx][ty]) return false;
tx --, ty ++, cnt ++;
}
return true;
}
void dfs (int x) { // x表示第x行
if (x == n) {
ans ++;
return ;
}
for (int i = 0;i < n;i ++) // 遍历每一列
if (!col[i] && check (x, i)) { // 如果这一列没被占,且左上三个之内、右上三个之内均不存在皇后
col[i] = 1;
vis[x][i] = 1;
dfs (x + 1);
vis[x][i] = 0;
col[i] = 0;
}
}
int main()
{
cin >> n;
dfs (0);
cout << ans << endl;
return 0;
}