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