AcWing 843. n-皇后问题 , 判断斜线的另一个写法
原题链接
中等
前言: 发现这个题如果用排列数字那个思路,其实就是多了一个检测斜线,所以我就想着把那个单独搞个判断就行了,也就是下面的check函数。
#include <string>
#include <vector>
#include <iostream>
#include<cmath>
typedef long long ll;
using namespace std;
const int N = 10;
int path[N];
bool used[N];//这俩数组的用法不变,path记录路径,used记录该位置是否已经被使用。
int n;
//这个check函数就是那个斜线判断了
//首先我们发现一个事情,path存的数字可以表示q在哪一列哪一行,例如path[1] = 2表示Q应该在第1行第二列的位置,也就是path可以得知前面存入Q的坐标
//既然知道前面存入的每个Q的坐标,那我按照二维的思维岂不是可以判断斜线上有没有其他Q了
//
bool check(int u, int i) {//传入当前存到哪一行了,和将要存入的列i
int sum = 1;//表示向上斜着格子的数量,初始为1个格子
while (u - sum >= 1) {
//这里想象一下,假如现在一共存了三行数据,也就是到path[3]了
//我需要判断path[1] 和path[2的Q是否与我当前给出的u,i在同一斜线
//在两个点在同一个斜线的条件就是,列的差==行的差,我突然发现这就是斜率为1的线
//行的差就是sum,当前列是i,要判断的列是path[u-sum],另外加上abs表示两个斜线,也就是斜率-1的也带上了
if (abs(path[u - sum] - i) == sum) return false;
sum++;//每次都加1,就是更向上判断
}
return true;//斜线上没有其他Q
}
void dfs(int u) {
if (u == n + 1) {//这里正常,也是到最后一层就把结果输出,是通过path的那个数得知当前行Q第几列。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (path[i] == j) cout << "Q";//意思是Q在第j列,那就第j个输出这个q,其他的输出.就行了。
else cout << '.';
}
cout << endl;
}
cout << endl;
}
for (int i = 1; i <= n; i++) {//枚举n个位置,看看哪个位置符合条件:没有被填 &&四个方向(横竖,两个方向斜线)都没有其他皇后
if (!used[i] && u > 1 && check(u, i) || u == 1) {//u==1的时候可以直接填,u!=1需要满足前三个条件
//特别说明一下,check是核心代码,只有u>1的时候才能check
path[u] = i;//意思是q放入第u行第i列
used[i] = true;
dfs(u + 1);
used[i] = false;
}
}
}
int main() {
cin >> n;
dfs(1);
return 0;
}
对于很大的数据,这样写时间复杂度比较高