for the backtracking part, thanks to the video of stanford cs106b lecture 10 by Julie Zelenski for the nice explanation of recursion and backtracking, highly recommended.
in hdu 2553 cout N-Queens solutions problem, dfs is used.
// please ignore, below analysis is inaccurate, though for inspiration considerations, I decided to let it remain.
and we use a extra occupied[] array to opimize the validation test, early termination when occupied[i]==1, and in function isSafe the test change from 3 to 2 comparisons.
for the improvement, here is an analysis:
noted that total call of dfs for n is less than factorial(n), for convenience we take as factorial(n),
in this appoach, in pow(n,n)-factorial(n) cases, we conduct one comparison, and three for others
otherwise, for all pow(n,n) cases, we must conduct three comparisons,
blow is a list for n from 1 to 10,
n n! n^n n!/n^n
1 1 1 1.00000
2 2 4 0.50000
3 6 27 0.22222
4 24 256 0.09375
5 120 3125 0.03840
6 720 46656 0.01543
7 5040 823543 0.00612
8 40320 16777216 0.00240
9 362880 387420489 0.00094
10 3628800 10000000000 0.00036
the table shows that, for almost all of the cases of large n (n>=4), we reduce 3 to 1 comparison in doing validation check.
occupied[i] is initilized to 0, before dfs, mark.
occupied[val]=1;
after dfs, unmark,
occupied[val]=0;
where val is the value chosen.
inspirations from chapter 3 Decompositions of graphs
in Algorithms(算法概论), Sanjoy Dasgupta University of California, San Diego Christos Papadimitriou University of California at Berkeley Umesh Vazirani University of California at Berkeley.
// leetcode N-Queens(12ms)
class Solution {
vector<vector<string>> ans;
int N;
//int numofsol;
void AddTo_ans(string &conf) {
vector<string> vecstrtmp;
string strtmp(N,'.');
for(auto ind: conf) {
vecstrtmp.push_back(strtmp);
vecstrtmp.back()[(size_t)ind-1]='Q';
}
ans.push_back(vector<string>());
ans.back().swap(vecstrtmp);
}
void RecListNQueens(string soFar, string rest) {
if(rest.empty()) {
//++numofsol;
AddTo_ans(soFar);
}
else {
int i,j,len=soFar.size(), flag;
for(i=0;i<rest.size();++i) {
for(j=0;j<len;++j) {
flag=1;
if(soFar[j]-rest[i]==len-j || soFar[j]-rest[i]==j-len) {
flag=0; break;
}
}
if(flag) RecListNQueens(soFar+rest[i],rest.substr(0,i)+rest.substr(i+1));
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
ans.clear();
//numofsol=0;
N=n;
string str;
for(int i=1;i<=n;++i) str.push_back(i);
RecListNQueens("", str);
return ans;
}
};
// with a tiny modification,
// leetcode N-Queens II (8ms)
class Solution {
//vector<vector<string>> ans;
int N;
int numofsol;
/*void AddTo_ans(string &conf) {
vector<string> vecstrtmp;
string strtmp(N,'.');
for(auto ind: conf) {
vecstrtmp.push_back(strtmp);
vecstrtmp.back()[(size_t)ind-1]='Q';
}
ans.push_back(vector<string>());
ans.back().swap(vecstrtmp);
}*/
void RecListNQueens(string soFar, string rest) {
if(rest.empty()) {
++numofsol;
//AddTo_ans(soFar);
}
else {
int i,j,len=soFar.size(), flag;
for(i=0;i<rest.size();++i) {
for(j=0;j<len;++j) {
flag=1;
if(soFar[j]-rest[i]==len-j || soFar[j]-rest[i]==j-len) {
flag=0; break;
}
}
if(flag) RecListNQueens(soFar+rest[i],rest.substr(0,i)+rest.substr(i+1));
}
}
}
public:
int totalNQueens(int n) {
//ans.clear();
numofsol=0;
N=n;
string str;
for(int i=1;i<=n;++i) str.push_back(i);
RecListNQueens("", str);
return numofsol;
}
};
// hdu 2553, 15ms
#include <cstdio>
#include <vector>
#include <algorithm>
class countNQueenSol {
static const int MAXN=12;
static int values[MAXN];
static int occupied[MAXN];
static std::vector<int> ans;
static int cnt, rownum;
static bool isSafe(int val, int row) {
for(int i=0;i<row;++i) {
if(val-values[i]==row-i || val-values[i]==i-row)
return false;
}
return true;
}
static void dfs(int row) {
if(row==rownum) ++cnt;
for(int i=0;i<rownum;++i) {
if(occupied[i]==0 && isSafe(i,row)) {
values[row]=i;
occupied[i]=1;
dfs(row+1);
occupied[i]=0;
}
}
}
public:
static int getMAXN() { return MAXN; }
static int solve(int k) {
if(k<=0 || k>=countNQueenSol::MAXN) return -1;
if(ans[k]<0) {
cnt=0;
rownum=k;
dfs(0);
//if(k==0) cnt=0; // adjust anomaly when k==0
ans[k]=cnt;
}
return ans[k];
}
};
int countNQueenSol::values[countNQueenSol::MAXN]={0};
int countNQueenSol::occupied[countNQueenSol::MAXN]={0};
std::vector<int> countNQueenSol::ans(countNQueenSol::MAXN,-1);
int countNQueenSol::cnt, countNQueenSol::rownum;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n;
while(scanf("%d",&n)==1 && n>0) {
printf("%d\n",countNQueenSol::solve(n));
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.
leetcode N-Queens/N-Queens II, backtracking, hdu 2553 count N-Queens, dfs 分类: leetcode hdoj 2015-07-09 02:07 102人阅读 评论(0) 收藏的更多相关文章
-
hdu 1082, stack emulation, and how to remove redundancy 分类: hdoj 2015-07-16 02:24 86人阅读 评论(0) 收藏
use fgets, and remove the potential '\n' in the string's last postion. (main point) remove redundanc ...
-
HDU 1272 小希的迷宫(并查集) 分类: 并查集 2015-07-07 23:38 2人阅读 评论(0) 收藏
Description 上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走.但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就 ...
-
one recursive approach for 3, hdu 1016 (with an improved version) , permutations, N-Queens puzzle 分类: hdoj 2015-07-19 16:49 86人阅读 评论(0) 收藏
one recursive approach to solve hdu 1016, list all permutations, solve N-Queens puzzle. reference: t ...
-
my understanding of (lower bound,upper bound) binary search, in C++, thanks to two post 分类: leetcode 2015-08-01 14:35 113人阅读 评论(0) 收藏
If you understand the comments below, never will you make mistakes with binary search! thanks to A s ...
-
hdu 1053 (huffman coding, greedy algorithm, std::partition, std::priority_queue ) 分类: hdoj 2015-06-18 19:11 22人阅读 评论(0) 收藏
huffman coding, greedy algorithm. std::priority_queue, std::partition, when i use the three commente ...
-
hdu 1052 (greedy algorithm) 分类: hdoj 2015-06-18 16:49 35人阅读 评论(0) 收藏
thanks to http://acm.hdu.edu.cn/discuss/problem/post/reply.php?action=support&postid=19638&m ...
-
hdu 1036 (I/O routines, fgets, sscanf, %02d, rounding, atoi, strtol) 分类: hdoj 2015-06-16 19:37 32人阅读 评论(0) 收藏
thanks to http://*.com/questions/2144459/using-scanf-to-accept-user-input and http://sta ...
-
A simple problem 分类: 哈希 HDU 2015-08-06 08:06 1人阅读 评论(0) 收藏
A simple problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) To ...
-
多校3- RGCDQ 分类: 比赛 HDU 2015-07-31 10:50 2人阅读 评论(0) 收藏
RGCDQ Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practic ...
随机推荐
-
js冒泡排序
今天面试了家公司,最后要写个js的简单数组排序,很久都写不出来,好尴尬,随着语言的发展,这些简单方法越来越不被重视了... <html> <head> <script t ...
-
webstorm IDE添加Plugins----添加vue插件
webstorm IDE很强大了,扩展性很强,语法校验很强大,不过有时候一些特殊的插件 还是需要自己添加到IDE的 下面以添加VUE Plugins 为例: Setting--Plugins[点下方 ...
-
android实现通过浏览器点击链接打开本地应用(APP)并拿到浏览器传递的数据
为了实现这个功能可折腾了我好久,先上一份代码,经楼主验证是绝对可以用的而且也比较清晰的代码!(ps:还是先剧透下吧,第三方大部分浏览器无法成功.) 点击浏览器中的URL链接,启动特定的App. 首先做 ...
-
css spprite应用
(一)实现简单的淘宝带图标侧边栏效果 <!DOCTYPE html> <html lang="en"> <head> <meta char ...
-
java.lang.NoClassDefFoundError: javax/servlet/ServletContext
方法1:把SpringBoot中main方法所在的class不再继承org.springframework.boot.context.web.SpringBootServletInitializer即 ...
-
【Oracle】虚拟表Dual
Dual是个虚拟表,用来构成SELECT语句的语法规则,Oracle保证Dual里面永远只有一条记录.可以用它来做很多事情,例如,查看当前用户:用来调用系统函数:得到序列的下一个值或者当前值:可以用作 ...
-
cesium加载纽约市3dtiles模型
const tileset = new Cesium.Cesium3DTileset({ url: '../../assets/data/NewYork/tileset.json' }); viewe ...
-
PHP数组——数组正则表达式、数组、预定义数组
正则表达式 1.替换 $s = "hello5world"; $s = preg_replace("/\d/","#",$s); echo ...
-
vue修改框架样式/deep/
/deep/ 父元素的样式名 /deep/ 要修改的样式名 使用 ... 貌似不行
-
D5 LCA 最近公共祖先
第一题: POJ 1330 Nearest Common Ancestors POJ 1330 这个题可不是以1为根节点,不看题就会一直wa呀: 加一个找根节点的措施: #include<alg ...