[已解决]DFS问题求调，如何优化？

额外减小

八皇后问题，见 https://www.luogu.com.cn/problem/P1219
最后一个点TLE,请问如何优化才能过呢
谢谢了
C++代码：

#include <iostream>
using namespace std;
int map[20][20],n,ans,out[3][20];

inline void change(int x,int y,int op)
{
        
        for(int i=0;i<n;i++)
        {
                map[i][y]+=op;
                map[x][i]+=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[x-i][y-i]+=op;
                if((x+i)>-1 and (y-i)>-1 and (x+i)<n and (y-i)<n) map[x+i][y-i]+=op;
        }
}

void dfs(int col)
{
        
        if(col==n-1)
        {
                for(int i=0;i<n;i++)
                {
                        if(!map[col][i])
                        {
                                if(ans<3)out[ans][col]=i+1;
                                ans++;
                        }
                }
        }
        else
        for(int i=0;i<n;i++)
        {
                if(!map[col][i])
                {
                        change(col,i,1);
                        if(ans<3)for(int j=ans;j<3;j++)out[j][col]=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[i][j]<<" ";
                }
                cout<<endl;
        }
        cout<<ans<<endl;
}

最佳答案

月排行榜 / 总排行榜

陶远航

2023-7-20 16:31:01

额外减小 发表于 2023-7-20 16:06
对不起，你这个代码连样例都过不了，所以我没办法给你最佳答案。

请慎用脚本！谢谢

这个再试试

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100],b[100],c[100],d[100];
int total;
int n;
int print()
{
    if(total<=2)
    {
        for(int k=1;k<=n;k++)
        cout<<a[k]<<" ";
        cout<<endl;
    }
    total++;
}
void queen(int i)
{
    if(i>n)
    {
        print();
        return;
    }
    else
    {
        for(int j=1;j<=n;j++)
        {
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))
            {
                a[i]=j;
                b[j]=1;
                c[i+j]=1;
                d[i-j+n]=1;
                queen(i+1);
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
            }
        }
    }
}
int main()
{    
    cin>>n;
    queen(1);
    cout<<total;
    return 0;
}

跳转到最佳答案楼层

陶远航

对于八皇后问题的优化，可以尝试使用剪枝技巧来减少搜索空间，以提高程序的效率。下面是对你给出的代码进行简单的优化：

#include <iostream>using namespace std;int map[20][20], n, ans, out[3][20];// 剪枝函数，判断当前位置是否可以放置皇后bool isSafe(int row, int col) {    for (int i = 0; i < col; i++) {        if (map[row][i])            return false;    }    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {        if (map[i][j])            return false;    }    for (int i = row, j = col; i < n && j >= 0; i++, j--) {        if (map[i][j])            return false;    }    return true;}void dfs(int col) {    if (col == n) {        for (int i = 0; i < n; i++) {            if (!map[i][col - 1]) {                if (ans < 3)                    out[ans][i] = col;                ans++;            }        }    } else {        for (int i = 0; i < n; i++) {            if (isSafe(i, col)) {                map[i][col] = 1;                if (ans < 3) {                    out[ans][col] = i + 1;                }                dfs(col + 1);                map[i][col] = 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[i][j] << " ";        }        cout << endl;    }    cout << ans << endl;    return 0;}

这里主要的优化点是使用isSafe()函数来判断当前位置是否可以放置皇后，避免不必要的搜索。同时，去掉了对change()函数的调用，简化了代码结构。

希望这些优化能够帮助你通过更多的测试用例！如有任何问题，请随时向我提问。

学习编程中的Ben

八皇后问题是一个经典的回溯算法问题，可以通过剪枝和优化来提高算法的效率。以下是几个可能的优化方法：

1. 使用位运算：在八皇后问题中，每一行只能放置一个皇后，可以使用一个整数的二进制表示来记录每一行皇后所在的列。这样可以用位运算来进行判断和操作，而不是使用二维数组 `map`。这样做可以提高程序的效率。

2. 剪枝策略：
   - 对角线冲突：如果两个皇后位于同一条对角线上，则它们的行下标之差等于列下标之差或相反数。可以使用一个数组来记录每条对角线上是否放置了皇后，以减少冲突的检查。
   - 竖直方向冲突：使用一个数组来记录每一列是否已经放置了皇后，以减少冲突的检查。
   - 提前终止：当已经找到了3组解时，可以及早退出递归搜索。

3. 优化搜索顺序：将搜索顺序从左到右改为从右到左，可以让程序更早地找到解，提前剪枝，减少不必要的搜索。

根据以上的优化方法，以下是对你给出的代码进行了修改和优化的示例：

```cpp
#include <iostream>
using namespace std;

int n, ans = 0;
int out[3][20];
int column[20] = {0}; // 记录列冲突
int diagonal1[40] = {0}; // 记录主对角线冲突
int diagonal2[40] = {0}; // 记录副对角线冲突

void dfs(int col) {
    if (col == n) {
        if (ans < 3) {
            for (int i = 0; i < n; i++) {
                out[ans][i] = column[i] + 1;
            }
        }
        ans++;
        return;
    }

    for (int i = n-1; i >= 0; i--) {  // 从右到左搜索
        if (!column[i] && !diagonal1[col-i+n] && !diagonal2[col+i]) {
            column[i] = 1;
            diagonal1[col-i+n] = 1;
            diagonal2[col+i] = 1;

            if (ans < 3) { // 只搜索前3个解
                for (int j = ans; j < 3; j++) {
                    out[j][col] = i + 1;
                }
                dfs(col + 1);
            } else {
                break; // 已经找到3个解，无需继续搜索
            }

            column[i] = 0;
            diagonal1[col-i+n] = 0;
            diagonal2[col+i] = 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[i][j] << " ";
        }
        cout << endl;
    }

    cout << ans << endl;
}
```

通过以上的优化，代码的效率应该会提高。希望能帮到你！如果还有其他问题，请随时提问。
求给个最佳答案呗

此回答源于ChatGPT，若有不正确之处，请多包容

isdkz

维数组来存储所有可能的攻击位置。

以下是一个优化后的C++代码实例：

#include <iostream>using namespace std;int n, ans = 0, a[3][20];bool col[20], dg[40], udg[40]; // 定义三个一维数组void dfs(int u) {    if (u == n) {        ans++;        if (ans <= 3) {            for (int i = 0; i < n; i++) {                a[ans - 1][ i] = col[ i];            }        }        return;    }    for (int i = 0; i < n; i++) {        if (!col[ i] && !dg[u + i] && !udg[n - u + i]) {            col[ i] = dg[u + i] = udg[n - u + i] = true;            if (ans < 3) a[ans][u] = i + 1;            dfs(u + 1);            // 恢复现场            col[ i] = dg[u + i] = udg[n - u + i] = false;        }    }}int main() {    cin >> n;    dfs(0);    for (int i = 0; i < 3; i++) {        for (int j = 0; j < n; j++) {            cout << a[ i][j] << " ";        }        cout << endl;    }    cout << ans << endl;}

这种优化方法的主要优点是减少了计算量。在原来的代码中，每次更新地图都需要O(n)的复杂度，而在新的代码中，我们只需要常数时间即可更新和恢复现场。

在新代码中， col[ i] 表示第i列是否有皇后， dg[u + i] 表示主对角线（左上到右下）上是否有皇后， udg[n - u + i] 表示副对角线（左下到右上）上是否有皇后。在 dfs 函数中，我们用回溯法枚举每一行的皇后放在哪一列，并用一维数组 col[] 、 dg[] 和 udg[] 记录是否在该列或对角线上已经放置了皇后。如果没有，我们就放置皇后并递归处理下一行；否则，我们就尝试下一列。

额外减小

刚学C++，语言基础不好，如有码风怪异的情况请见谅

额外减小

呵呵，你们为什么都喜欢用脚本？

liuhongrun2022

不会cpp（悲）

sfqxx

同7#（悲）

学习编程中的Ben

额外减小 发表于 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.看来你的脚本比他们的略逊一筹

学习编程中的Ben

额外减小 发表于 2023-7-20 16:10
对不起，您提供的代码连编译都过不了，请你好自为之吧！

请慎用脚本，谢谢

煞笔ChatGPT

额外减小

学习编程中的Ben 发表于 2023-7-20 16:11
煞笔ChatGPT

六

学习编程中的Ben

额外减小 发表于 2023-7-20 16:12
六

就是ChatGPT是傻逼

额外减小

@zhangjinxuan @元豪 @高山 @Mike_python小

陶远航

额外减小 发表于 2023-7-20 16:06
对不起，你这个代码连样例都过不了，所以我没办法给你最佳答案。

请慎用脚本！谢谢

这个再试试

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100],b[100],c[100],d[100];
int total;
int n;
int print()
{
    if(total<=2)
    {
        for(int k=1;k<=n;k++)
        cout<<a[k]<<" ";
        cout<<endl;
    }
    total++;
}
void queen(int i)
{
    if(i>n)
    {
        print();
        return;
    }
    else
    {
        for(int j=1;j<=n;j++)
        {
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))
            {
                a[i]=j;
                b[j]=1;
                c[i+j]=1;
                d[i-j+n]=1;
                queen(i+1);
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
            }
        }
    }
}
int main()
{    
    cin>>n;
    queen(1);
    cout<<total;
    return 0;
}

额外减小

陶远航 发表于 2023-7-20 16:31
这个再试试

可以过，效率也很高。我再考虑一下

陶远航

额外减小 发表于 2023-7-20 16:44
可以过，效率也很高。我再考虑一下

考虑啥呀，最佳给我呗...

sfqxx

额外减小 发表于 2023-7-20 16:44
可以过，效率也很高。我再考虑一下

先看看是不是题解