N皇后问题(DFS) HDU - 2553【详记】

2024-03-22 18:40
文章标签 问题 dfs 皇后 hdu 2553 详记

本文主要是介绍N皇后问题(DFS) HDU - 2553【详记】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

如果不太懂DFS,可以试着用递归写个代码输出组合(例如输入3,输出123,1,2,3,12,13,23),就是排列组合中的组合,应该对理解这种思想有帮助:

1、使用DFS(深搜)遍历所有的序列所有的子组合(子序列)(排列组合中的组合)https://blog.csdn.net/qq_41246972/article/details/86750594

2、DFS——组合与排列
https://blog.csdn.net/cqbzlytina/article/details/78646018#枚举组合combination

先放一下AC代码,这应该算是比较经典的问题,也有人称这个解决方法叫回溯,有什么大区别呢,其实我不太懂,欢迎懂的大佬留个言赐个教,3x了!
我的代码比较乱~~因为中间始终无法完美解决,又去找了类似的八皇后问题,N Queens问题,哈哈!
话不多说,先放AC代码:(下面还有整理了一下的更整齐的代码)

#include<iostream> 
#include<vector>
#include<algorithm>
using namespace std; 
int n,ans=0,visit[10*10];
int ans1[100000];
vector<string> ans_vec;
int is_here_ok(int line,int j)
{ for(int i=0;i<line;i++) if((visit[i]==j)||(visit[i]==j-line+i)||(visit[i]==j+line-i)) return 0;    return 1;
}
void dfs(int line)
{if(line==n){ans++;  string res="";for(int i=0;i<n;i++) res+="#";for(int i=0;i<n;i++) res[i]='0'+visit[i];ans_vec.push_back(res); return;}for(int j=0;j<n;j++)if(is_here_ok(line,j)==1){visit[line]=j;dfs(line+1);}else continue;
}
bool cmp(string a,string b)
{return a<b;
}
int main()
{for(int i=0;i<10;i++) visit[i]=0;for(int i=0;i<20;i++) ans1[i]=-99;while(true){ int a=INT_MAX;cin>>n; getchar();if(n==0) return 0; ans=0;if(ans1[n]==-99){dfs(0);ans1[n]=ans;}cout<<ans1[n]<<endl;// sort(ans_vec.begin(),ans_vec.end(),cmp);// for(int i=0;i<ans;i++)// {//     string res=ans_vec[i];//     int len=res.length();//     for(int j=0;j<len;j++)//     {//         int k=(int)(char)res[j]-'0';//         cout<<k+1;//     }//     cout<<endl;// }//break;// cout<<ans<<endl;// int anslist[]={1,0,0,2,10,4,40,92,352,724};// cout<<anslist[n-1]<<endl;} return 0;
}

从被注释的代码可以看出,因为题目只有10“ ”数据,所以我打表了,嘿嘿!
为什么“ ”要加引号呢?因为准确说,应该是10 ☆ ☆,而不是10个!正是如此我才超时了好久!
且听我细细道来:
一开始我参考了网上代码后写出来感觉颇为满意,答案也是对的,难耐却超时了!于是试了一下网上的代码( https://www.cnblogs.com/I-love-HLD/p/4624658.html ),发现不仅仅没有超时,而且还超级快!几十毫秒,但是没仔细看此人的代码,去网上找了别人的文章(主要是 https://blog.csdn.net/hackbuteer1/article/details/6657109 ,前面写了一大段,挨个看发现其实差不多),看来看去感觉思路和我的都差不多,挨个试一下发现不打表的话都超时,只有上面第二个链接里用了目前解决八皇后问题最高效的位运算的方法没有超时,大几百毫秒,还是抵不上一开始那个大神的几十毫秒,于是就奇怪了,回头看那段代码:

发现他这check()函数超短,于是以为这个原因,开始以膜拜的眼光阅读,发现原来循环在下面,思路还是一样!
靠!什么鬼!

再仔细看,才发现这题坑人之处!神经病!靠!原来题目的测试数据有很多重复,导致大量多余运算,例如输入了5,可能过会又来!原来那位朋友将答案存了起来,如果已经算过了就不算了,怪不得我在“把玩”他的代码的时候发现第一次输入15要算好久,第二次一下子就出来了!我还以为是C++自己优化避免不必要的重复运算

(网上还有人貌似还没发现为什么自己的只能“离线”,别人的可以直接AC ,,,,,XD)

于是我也像他那样,就AC了,当然,打表也挺好的!

接下来再去学习一下使用位运算来求解N皇后的高效算法(这题浪费了好多时间!)
文章开头的AC代码整理了一下,看上去更清爽

#include<iostream>   
using namespace std; 
int n,ans=0,visit[1000],ans_array[1000]; 
bool is_here_ok(int line,int j)
{ for(int i=0;i<line;i++) if((visit[i]==j)||(visit[i]==j-line+i)||(visit[i]==j+line-i)) return false;    return true;
}
void dfs(int line)
{if(line==n){ans++;   return;}for(int j=0;j<n;j++)if(is_here_ok(line,j)){visit[line]=j;dfs(line+1);}else continue;
} 
int main()
{ for(int i=0;i<1000;i++) ans_array[i]=-1;while(true){  cin>>n; getchar();if(n==0) break;ans=0;if(ans_array[n]==-1){dfs(0); ans_array[n]=ans;}cout<<ans_array[n]<<endl; } return 0;
}

这篇关于N皇后问题(DFS) HDU - 2553【详记】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/835967

相关文章

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr