hdu2553n皇后------回溯算法
算法 ------ 回溯 皇后
2023-09-11 14:22:51 时间
定义:
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。
但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<cmath> #include<stdlib.h> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<iomanip> using namespace std; int N; int a[11]; int ans; //i表示第几行,a[i]表示第几列 bool judge(int r) { for(int i=1;i<r;i++) { if(a[r]==a[i]||abs(a[r]-a[i])==abs(i-r)) return 0; } return 1; } void hang(int r) { if(r>N) ans++; else { for(int i=1;i<=N;i++)//遍历第r行的所有列。 { a[r]=i; if(judge(r)) hang(r+1); } } } int main() { while(cin>>N&&N!=0) { ans=0; hang(1); cout<<ans<<endl; } return 0; }
i代表第几行,a[i]代表第几列,递推。
从第一行开始放,然后遍历每一列。同时还要检查一下之前的每行是否会和现在放的这个发生冲突。(不能在同一列,不能在对角线上)
这行的这列可以放,那么继续下一行。
注意这个问题用上述代码超时了,所以看一下范围,n小于等于10 ,所以采用打表的方式,算出来所有结果放在一个数组里面。
相关文章
- 数据结构与算法(周鹏-未出版)-第六章 树-6.3 二叉树基本操作的实现
- 【算法】【字符串模块】判断括号字符串是否有效,如果无效则求最长的有效长度
- 国密SM3算法在linux和windows平台结果不一致问题
- K-近邻算法之交叉验证,网格搜索
- 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
- [转]算法的复杂度
- 字符串查找算法总结(暴力匹配、KMP 算法、Boyer-Moore 算法和 Sunday 算法)
- Knuth大神教您学习算法 (计算机程序设计艺术P4)
- 基于浅层神经网络(全连接网络)的强化学习算法(Reinforce) 在训练过程中出现梯度衰退(degenerate)的现象
- 多目标遗传算法 ------ NSGA-II (部分源码解析)README 算法的部分英文解释
- ACM算法总结及刷题参考
- 【基础算法】基础算法【转载】
- 华为OD机试 -括号匹配(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 桶排序算法
- 数据挖掘十大经典算法
- 操作系统算法整理+汇总