N皇后问题优化
本帖最后由 柿子饼同学 于 2022-6-28 14:12 编辑我的代码贴上, 主要 n = 13 的时候超时了 , 也不是很理解题解中的二进制优化 . 可以详细解释下嘛 , 谢谢
题目::https://www.luogu.com.cn/problem/P1219
题解::https://www.luogu.com.cn/problem/solution/P1219
#include <bits/stdc++.h>
using namespace std;
int n, ans = 0, cnt = 1; // n个皇后, ans个解法
int xys = {0}; // 它的下标是 行 , 存储的值是 列
bool check(int x, int y, int dep){ // 检查放的位置是否符合
for(int i = 1; i < dep; i++){ // 同行列 , 对角线
if(x == xys || y == i || x+y == xys+i || x-y == xys-i) return 0;
}
return 1;
}
void print(){ // 输出
for(int i = 1; i <= n; i++){
cout << xys << " ";
}
cout << endl;
}
void dfs(int dep){
if(dep > n){
if(ans <= 3) print(); // 输出前 3 组解法
ans++; // 到头就走 , 总解法加一
return;
}
else{
for(int i = 1; i <= n; i++){
if(check(i, dep, dep)){ // 符合条件就放
xys = i;
dfs(dep+1);
xys = 0; // 回溯
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin >> n;
dfs(1);
cout << ans << endl;
return 0;
}{:10_266:}
(话说 N 皇后只能用暴力算法嘛) 就是用这种递归的方法解的，换别的方法我就不会了，我没发现二进制优化部分。如果实在不懂可以画张图。 桃花飞舞 发表于 2022-6-28 19:45
就是用这种递归的方法解的，换别的方法我就不会了，我没发现二进制优化部分。如果实在不懂可以画张图。
哦哦哦 , 普通做法我懂 , 谢谢
主要想学习下优化 用 4 个数组过了 , 但是二进制依然不会{:10_266:} 是这样吗？我也不知道对不对：#include <iostream>
using namespace std;
int board;
// 打印棋盘上皇后的位置
int show(int N) {
for(int i = 1; i <= N; i++) {
cout << board << " ";
}
cout << endl;
return 0;
}
// 检查棋盘上的每个直线位置是否存在多个皇后
bool check(int k) {
for (int i = 1; i < k; ++i) {
if ((board == board) or (board - board == k - i) or (board - board == i - k)) return false;
}
return true;
}
// 题解
int solution(int N) {
int k = 1, count = 0;
board = 1; // 从 (1, 1) 开始
while(k > 0) {
if(k <= N and board <= N) {
if(not check(k)) board++;
else {
k++; // 往右移
board = 1; // 放置皇后
}
}
else {
if(k > N) {
count++; // 计算解的总数
if (count < 4) show(N); // 打印前三个解
}
k--;
board++;
}
}
return count;
}
int main(void) {
int N = 13;
cout << solution(N);
return 0;
} 二进制优化主要是优化o(1)的指令周期数，对算法整体复杂度不构成影响（但是会更快）
建议把所有cin/cout换成scanf/pirntf会更快
在开头只引用iostream和cstdio也可增快速度
另：n皇后目前只能递归做 ExiaGN001 发表于 2022-6-29 22:18
二进制优化主要是优化o(1)的指令周期数，对算法整体复杂度不构成影响（但是会更快）
建议把所有cin/cout换 ...
楼主已经加了 ios::sync_with_stdio(0); ExiaGN001 发表于 2022-6-29 22:18
二进制优化主要是优化o(1)的指令周期数，对算法整体复杂度不构成影响（但是会更快）
建议把所有cin/cout换 ...
好的 , 谢谢回答
傻眼貓咪 发表于 2022-6-30 09:47
楼主已经加了 ios::sync_with_stdio(0);
C格式输入输出已经成习惯了
所以我一直都不常用cin/cout
ExiaGN001 发表于 2022-6-30 19:44
C格式输入输出已经成习惯了
所以我一直都不常用cin/cout
{:10_254:} 傻眼貓咪 发表于 2022-6-30 20:28
主要是我电脑上一用cin/cout就会触发Windows Defender报毒
所以只能用printf,scanf,putchar,puts,getchar,gets,fprintf,fscanf这些函数 ExiaGN001 发表于 2022-7-1 06:45
主要是我电脑上一用cin/cout就会触发Windows Defender报毒
所以只能用printf,scanf,putchar,puts,getcha ...
我不知道你的问题是不是和以下有关？希望对你有帮助。
现在的防毒软件可说是越来越敏感了，基本上只要运行代码就会触发防毒软件的，防毒软件会误以为是病毒入侵，因此杀项目。网络上很多方法，比如：Shellcode免杀等设定。
页:
[1]