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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符