DFS问题求调，如何优化？
八皇后问题，见 https://www.luogu.com.cn/problem/P1219最后一个点TLE,请问如何优化才能过呢
谢谢了
C++代码：
#include <iostream>
using namespace std;
int map,n,ans,out;
inline void change(int x,int y,int op)
{
for(int i=0;i<n;i++)
{
map+=op;
map+=op;
}
for(int i=1-n;i<n;i++)
{
if((x-i)>-1 and (y-i)>-1 and (x-i)<n and (y-i)<n) map+=op;
if((x+i)>-1 and (y-i)>-1 and (x+i)<n and (y-i)<n) map+=op;
}
}
void dfs(int col)
{
if(col==n-1)
{
for(int i=0;i<n;i++)
{
if(!map)
{
if(ans<3)out=i+1;
ans++;
}
}
}
else
for(int i=0;i<n;i++)
{
if(!map)
{
change(col,i,1);
if(ans<3)for(int j=ans;j<3;j++)out=i+1;
dfs(col+1);
change(col,i,-1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(),cout.tie();
cin>>n;
dfs(0);
for(int i=0;i<3;i++)
{
for(int j=0;j<n;j++)
{
cout<<out<<" ";
}
cout<<endl;
}
cout<<ans<<endl;
} 对于八皇后问题的优化，可以尝试使用剪枝技巧来减少搜索空间，以提高程序的效率。下面是对你给出的代码进行简单的优化：
#include <iostream>
using namespace std;
int map, n, ans, out;
// 剪枝函数，判断当前位置是否可以放置皇后
bool isSafe(int row, int col) {
for (int i = 0; i < col; i++) {
if (map)
return false;
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (map)
return false;
}
for (int i = row, j = col; i < n && j >= 0; i++, j--) {
if (map)
return false;
}
return true;
}
void dfs(int col) {
if (col == n) {
for (int i = 0; i < n; i++) {
if (!map) {
if (ans < 3)
out = col;
ans++;
}
}
} else {
for (int i = 0; i < n; i++) {
if (isSafe(i, col)) {
map = 1;
if (ans < 3) {
out = i + 1;
}
dfs(col + 1);
map = 0;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
dfs(0);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cout << out << " ";
}
cout << endl;
}
cout << ans << endl;
return 0;
}
这里主要的优化点是使用isSafe()函数来判断当前位置是否可以放置皇后，避免不必要的搜索。同时，去掉了对change()函数的调用，简化了代码结构。
希望这些优化能够帮助你通过更多的测试用例！如有任何问题，请随时向我提问。 八皇后问题是一个经典的回溯算法问题，可以通过剪枝和优化来提高算法的效率。以下是几个可能的优化方法：
1. 使用位运算：在八皇后问题中，每一行只能放置一个皇后，可以使用一个整数的二进制表示来记录每一行皇后所在的列。这样可以用位运算来进行判断和操作，而不是使用二维数组 `map`。这样做可以提高程序的效率。
2. 剪枝策略：
- 对角线冲突：如果两个皇后位于同一条对角线上，则它们的行下标之差等于列下标之差或相反数。可以使用一个数组来记录每条对角线上是否放置了皇后，以减少冲突的检查。
- 竖直方向冲突：使用一个数组来记录每一列是否已经放置了皇后，以减少冲突的检查。
- 提前终止：当已经找到了3组解时，可以及早退出递归搜索。
3. 优化搜索顺序：将搜索顺序从左到右改为从右到左，可以让程序更早地找到解，提前剪枝，减少不必要的搜索。
根据以上的优化方法，以下是对你给出的代码进行了修改和优化的示例：
```cpp
#include <iostream>
using namespace std;
int n, ans = 0;
int out;
int column = {0}; // 记录列冲突
int diagonal1 = {0}; // 记录主对角线冲突
int diagonal2 = {0}; // 记录副对角线冲突
void dfs(int col) {
if (col == n) {
if (ans < 3) {
for (int i = 0; i < n; i++) {
out = column + 1;
}
}
ans++;
return;
}
for (int i = n-1; i >= 0; i--) {// 从右到左搜索
if (!column && !diagonal1 && !diagonal2) {
column = 1;
diagonal1 = 1;
diagonal2 = 1;
if (ans < 3) { // 只搜索前3个解
for (int j = ans; j < 3; j++) {
out = i + 1;
}
dfs(col + 1);
} else {
break; // 已经找到3个解，无需继续搜索
}
column = 0;
diagonal1 = 0;
diagonal2 = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(),cout.tie();
cin >> n;
dfs(0);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cout << out << " ";
}
cout << endl;
}
cout << ans << endl;
}
```
通过以上的优化，代码的效率应该会提高。希望能帮到你！如果还有其他问题，请随时提问。
求给个最佳答案呗{:10_254:}
此回答源于ChatGPT，若有不正确之处，请多包容 维数组来存储所有可能的攻击位置。
以下是一个优化后的C++代码实例：
#include <iostream>
using namespace std;
int n, ans = 0, a;
bool col, dg, udg; // 定义三个一维数组
void dfs(int u) {
if (u == n) {
ans++;
if (ans <= 3) {
for (int i = 0; i < n; i++) {
a[ i] = col[ i];
}
}
return;
}
for (int i = 0; i < n; i++) {
if (!col[ i] && !dg && !udg) {
col[ i] = dg = udg = true;
if (ans < 3) a = i + 1;
dfs(u + 1);
// 恢复现场
col[ i] = dg = udg = false;
}
}
}
int main() {
cin >> n;
dfs(0);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cout << a[ i] << " ";
}
cout << endl;
}
cout << ans << endl;
}
这种优化方法的主要优点是减少了计算量。在原来的代码中，每次更新地图都需要O(n)的复杂度，而在新的代码中，我们只需要常数时间即可更新和恢复现场。
在新代码中， col[ i] 表示第i列是否有皇后， dg 表示主对角线（左上到右下）上是否有皇后， udg 表示副对角线（左下到右上）上是否有皇后。在 dfs 函数中，我们用回溯法枚举每一行的皇后放在哪一列，并用一维数组 col[] 、 dg[] 和 udg[] 记录是否在该列或对角线上已经放置了皇后。如果没有，我们就放置皇后并递归处理下一行；否则，我们就尝试下一列。 刚学C++，语言基础不好，如有码风怪异的情况请见谅 呵呵，你们为什么都喜欢用脚本？ 不会cpp（悲） 同7#（悲） 额外减小 发表于 2023-7-20 16:00
呵呵，你们为什么都喜欢用脚本？
同7#(悲) 陶远航 发表于 2023-7-20 15:58
对于八皇后问题的优化，可以尝试使用剪枝技巧来减少搜索空间，以提高程序的效率。下面是对你给出的代码进行 ...
对不起，你这个代码连样例都过不了，所以我没办法给你最佳答案。
请慎用脚本！谢谢 isdkz 发表于 2023-7-20 15:58
维数组来存储所有可能的攻击位置。
以下是一个优化后的C++代码实例：
对不起，你这个代码连样例都过不了，所以我没办法给你最佳答案。
请慎用脚本！谢谢 学习编程中的Ben 发表于 2023-7-20 15:58
八皇后问题是一个经典的回溯算法问题，可以通过剪枝和优化来提高算法的效率。以下是几个可能的优化方法：
...
对不起，您提供的代码连编译都过不了，请你好自为之吧！
请慎用脚本，谢谢
ps.看来你的脚本比他们的略逊一筹 额外减小 发表于 2023-7-20 16:10
对不起，您提供的代码连编译都过不了，请你好自为之吧！
请慎用脚本，谢谢
煞笔ChatGPT 学习编程中的Ben 发表于 2023-7-20 16:11
煞笔ChatGPT
六 额外减小 发表于 2023-7-20 16:12
六
就是ChatGPT是傻逼 @zhangjinxuan @元豪 @高山 @Mike_python小 本帖最后由 陶远航 于 2023-7-20 16:32 编辑
额外减小 发表于 2023-7-20 16:06
对不起，你这个代码连样例都过不了，所以我没办法给你最佳答案。
请慎用脚本！谢谢
这个再试试
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int a,b,c,d;
int total;
int n;
int print()
{
if(total<=2)
{
for(int k=1;k<=n;k++)
cout<<a<<" ";
cout<<endl;
}
total++;
}
void queen(int i)
{
if(i>n)
{
print();
return;
}
else
{
for(int j=1;j<=n;j++)
{
if((!b)&&(!c)&&(!d))
{
a=j;
b=1;
c=1;
d=1;
queen(i+1);
b=0;
c=0;
d=0;
}
}
}
}
int main()
{
cin>>n;
queen(1);
cout<<total;
return 0;
} 陶远航 发表于 2023-7-20 16:31
这个再试试
可以过，效率也很高。我再考虑一下 额外减小 发表于 2023-7-20 16:44
可以过，效率也很高。我再考虑一下
考虑啥呀，最佳给我呗... 额外减小 发表于 2023-7-20 16:44
可以过，效率也很高。我再考虑一下
先看看是不是题解
页:
[1]
2