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

额外减小

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

1. #include <iostream>
   
2. using namespace std;
   
3. int map[20][20],n,ans,out[3][20];
   
4. 
   
5. inline void change(int x,int y,int op)
   
6. {
   
7.        
   
8.         for(int i=0;i<n;i++)
   
9.         {
   
10.                 map[i][y]+=op;
    
11.                 map[x][i]+=op;
    
12.                
    
13.         }
    
14.         for(int i=1-n;i<n;i++)
    
15.         {
    
16.                 if((x-i)>-1 and (y-i)>-1 and (x-i)<n and (y-i)<n) map[x-i][y-i]+=op;
    
17.                 if((x+i)>-1 and (y-i)>-1 and (x+i)<n and (y-i)<n) map[x+i][y-i]+=op;
    
18.         }
    
19. }
    
20. 
    
21. void dfs(int col)
    
22. {
    
23.        
    
24.         if(col==n-1)
    
25.         {
    
26.                 for(int i=0;i<n;i++)
    
27.                 {
    
28.                         if(!map[col][i])
    
29.                         {
    
30.                                 if(ans<3)out[ans][col]=i+1;
    
31.                                 ans++;
    
32.                         }
    
33.                 }
    
34.         }
    
35.         else
    
36.         for(int i=0;i<n;i++)
    
37.         {
    
38.                 if(!map[col][i])
    
39.                 {
    
40.                         change(col,i,1);
    
41.                         if(ans<3)for(int j=ans;j<3;j++)out[j][col]=i+1;
    
42.                         dfs(col+1);
    
43.                        
    
44.                         change(col,i,-1);
    
45.                 }
    
46.         }
    
47. }
    
48. 
    
49. int main()
    
50. {
    
51.         ios::sync_with_stdio(false);
    
52.         cin.tie(),cout.tie();
    
53.         cin>>n;
    
54.         dfs(0);
    
55.         for(int i=0;i<3;i++)
    
56.         {
    
57.                 for(int j=0;j<n;j++)
    
58.                 {
    
59.                         cout<<out[i][j]<<" ";
    
60.                 }
    
61.                 cout<<endl;
    
62.         }
    
63.         cout<<ans<<endl;
    
64. }

复制代码

最佳答案

月排行榜 / 总排行榜

陶远航

2023-7-20 16:31:01

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

请慎用脚本！谢谢

这个再试试

1. #include<iostream>
   
2. #include<cstdlib>
   
3. #include<cstdio>
   
4. #include<cmath>
   
5. using namespace std;
   
6. int a[100],b[100],c[100],d[100];
   
7. int total;
   
8. int n;
   
9. int print()
   
10. {
    
11.     if(total<=2)
    
12.     {
    
13.         for(int k=1;k<=n;k++)
    
14.         cout<<a[k]<<" ";
    
15.         cout<<endl;
    
16.     }
    
17.     total++;
    
18. }
    
19. void queen(int i)
    
20. {
    
21.     if(i>n)
    
22.     {
    
23.         print();
    
24.         return;
    
25.     }
    
26.     else
    
27.     {
    
28.         for(int j=1;j<=n;j++)
    
29.         {
    
30.             if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))
    
31.             {
    
32.                 a[i]=j;
    
33.                 b[j]=1;
    
34.                 c[i+j]=1;
    
35.                 d[i-j+n]=1;
    
36.                 queen(i+1);
    
37.                 b[j]=0;
    
38.                 c[i+j]=0;
    
39.                 d[i-j+n]=0;
    
40.             }
    
41.         }
    
42.     }
    
43. }
    
44. int main()
    
45. {   
    
46.     cin>>n;
    
47.     queen(1);
    
48.     cout<<total;
    
49.     return 0;
    
50. }

复制代码

跳转到最佳答案楼层

陶远航

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

1. #include <iostream>
2. using namespace std;
4. int map[20][20], n, ans, out[3][20];
6. // 剪枝函数，判断当前位置是否可以放置皇后
7. bool isSafe(int row, int col) {
8.     for (int i = 0; i < col; i++) {
9.         if (map[row][i])
10.             return false;
11.     }
12.     for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
13.         if (map[i][j])
14.             return false;
15.     }
16.     for (int i = row, j = col; i < n && j >= 0; i++, j--) {
17.         if (map[i][j])
18.             return false;
19.     }
20.     return true;
21. }
23. void dfs(int col) {
24.     if (col == n) {
25.         for (int i = 0; i < n; i++) {
26.             if (!map[i][col - 1]) {
27.                 if (ans < 3)
28.                     out[ans][i] = col;
29.                 ans++;
30.             }
31.         }
32.     } else {
33.         for (int i = 0; i < n; i++) {
34.             if (isSafe(i, col)) {
35.                 map[i][col] = 1;
36.                 if (ans < 3) {
37.                     out[ans][col] = i + 1;
38.                 }
39.                 dfs(col + 1);
40.                 map[i][col] = 0;
41.             }
42.         }
43.     }
44. }
46. int main() {
47.     ios::sync_with_stdio(false);
48.     cin.tie(0), cout.tie(0);
49.     cin >> n;
50.     dfs(0);
51.     for (int i = 0; i < 3; i++) {
52.         for (int j = 0; j < n; j++) {
53.             cout << out[i][j] << " ";
54.         }
55.         cout << endl;
56.     }
57.     cout << ans << endl;
58.     return 0;
59. }

复制代码

这里主要的优化点是使用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++代码实例：

1. #include <iostream>
2. using namespace std;
4. int n, ans = 0, a[3][20];
5. bool col[20], dg[40], udg[40]; // 定义三个一维数组
7. void dfs(int u) {
8.     if (u == n) {
9.         ans++;
10.         if (ans <= 3) {
11.             for (int i = 0; i < n; i++) {
12.                 a[ans - 1][ i] = col[ i];
13.             }
14.         }
15.         return;
16.     }
17.     for (int i = 0; i < n; i++) {
18.         if (!col[ i] && !dg[u + i] && !udg[n - u + i]) {
19.             col[ i] = dg[u + i] = udg[n - u + i] = true;
20.             if (ans < 3) a[ans][u] = i + 1;
21.             dfs(u + 1);
22.             // 恢复现场
23.             col[ i] = dg[u + i] = udg[n - u + i] = false;
24.         }
25.     }
26. }
28. int main() {
29.     cin >> n;
30.     dfs(0);
31.     for (int i = 0; i < 3; i++) {
32.         for (int j = 0; j < n; j++) {
33.             cout << a[ i][j] << " ";
34.         }
35.         cout << endl;
36.     }
37.     cout << ans << endl;
38. }

复制代码

这种优化方法的主要优点是减少了计算量。在原来的代码中，每次更新地图都需要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
对不起，你这个代码连样例都过不了，所以我没办法给你最佳答案。

请慎用脚本！谢谢

这个再试试

1. #include<iostream>
   
2. #include<cstdlib>
   
3. #include<cstdio>
   
4. #include<cmath>
   
5. using namespace std;
   
6. int a[100],b[100],c[100],d[100];
   
7. int total;
   
8. int n;
   
9. int print()
   
10. {
    
11.     if(total<=2)
    
12.     {
    
13.         for(int k=1;k<=n;k++)
    
14.         cout<<a[k]<<" ";
    
15.         cout<<endl;
    
16.     }
    
17.     total++;
    
18. }
    
19. void queen(int i)
    
20. {
    
21.     if(i>n)
    
22.     {
    
23.         print();
    
24.         return;
    
25.     }
    
26.     else
    
27.     {
    
28.         for(int j=1;j<=n;j++)
    
29.         {
    
30.             if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))
    
31.             {
    
32.                 a[i]=j;
    
33.                 b[j]=1;
    
34.                 c[i+j]=1;
    
35.                 d[i-j+n]=1;
    
36.                 queen(i+1);
    
37.                 b[j]=0;
    
38.                 c[i+j]=0;
    
39.                 d[i-j+n]=0;
    
40.             }
    
41.         }
    
42.     }
    
43. }
    
44. int main()
    
45. {   
    
46.     cin>>n;
    
47.     queen(1);
    
48.     cout<<total;
    
49.     return 0;
    
50. }

复制代码

额外减小

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

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

陶远航

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

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

sfqxx

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

先看看是不是题解