leetcode N-Queens/N-Queens II, backtracking, hdu 2553 count N-Queens, dfs 分类: leetcode hdoj 2015-07-09 02:07 102人阅读 评论(0) 收藏

时间:2022-09-24 08:34:49
  1. 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.

  2. 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) 收藏的更多相关文章

  1. hdu 1082&comma; stack emulation&comma; and how to remove redundancy 分类: hdoj 2015-07-16 02&colon;24 86人阅读 评论&lpar;0&rpar; 收藏

    use fgets, and remove the potential '\n' in the string's last postion. (main point) remove redundanc ...

  2. HDU 1272 小希的迷宫(并查集) 分类: 并查集 2015-07-07 23&colon;38 2人阅读 评论&lpar;0&rpar; 收藏

    Description 上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走.但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就 ...

  3. one recursive approach for 3&comma; hdu 1016 &lpar;with an improved version&rpar; &comma; permutations&comma; N-Queens puzzle 分类: hdoj 2015-07-19 16&colon;49 86人阅读 评论&lpar;0&rpar; 收藏

    one recursive approach to solve hdu 1016, list all permutations, solve N-Queens puzzle. reference: t ...

  4. my understanding of &lpar;lower bound&comma;upper bound&rpar; binary search&comma; in C&plus;&plus;&comma; thanks to two post 分类: leetcode 2015-08-01 14&colon;35 113人阅读 评论&lpar;0&rpar; 收藏

    If you understand the comments below, never will you make mistakes with binary search! thanks to A s ...

  5. hdu 1053 &lpar;huffman coding&comma; greedy algorithm&comma; std&colon;&colon;partition&comma; std&colon;&colon;priority&lowbar;queue &rpar; 分类: hdoj 2015-06-18 19&colon;11 22人阅读 评论&lpar;0&rpar; 收藏

    huffman coding, greedy algorithm. std::priority_queue, std::partition, when i use the three commente ...

  6. hdu 1052 &lpar;greedy algorithm&rpar; 分类: hdoj 2015-06-18 16&colon;49 35人阅读 评论&lpar;0&rpar; 收藏

    thanks to http://acm.hdu.edu.cn/discuss/problem/post/reply.php?action=support&postid=19638&m ...

  7. hdu 1036 &lpar;I&sol;O routines&comma; fgets&comma; sscanf&comma; &percnt;02d&comma; rounding&comma; atoi&comma; strtol&rpar; 分类: hdoj 2015-06-16 19&colon;37 32人阅读 评论&lpar;0&rpar; 收藏

    thanks to http://*.com/questions/2144459/using-scanf-to-accept-user-input and http://sta ...

  8. A simple problem 分类: 哈希 HDU 2015-08-06 08&colon;06 1人阅读 评论&lpar;0&rpar; 收藏

    A simple problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) To ...

  9. 多校3- RGCDQ 分类: 比赛 HDU 2015-07-31 10&colon;50 2人阅读 评论&lpar;0&rpar; 收藏

    RGCDQ Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practic ...

随机推荐

  1. js冒泡排序

    今天面试了家公司,最后要写个js的简单数组排序,很久都写不出来,好尴尬,随着语言的发展,这些简单方法越来越不被重视了... <html> <head> <script t ...

  2. webstorm IDE添加Plugins----添加vue插件

    webstorm IDE很强大了,扩展性很强,语法校验很强大,不过有时候一些特殊的插件  还是需要自己添加到IDE的 下面以添加VUE Plugins 为例: Setting--Plugins[点下方 ...

  3. android实现通过浏览器点击链接打开本地应用(APP)并拿到浏览器传递的数据

    为了实现这个功能可折腾了我好久,先上一份代码,经楼主验证是绝对可以用的而且也比较清晰的代码!(ps:还是先剧透下吧,第三方大部分浏览器无法成功.) 点击浏览器中的URL链接,启动特定的App. 首先做 ...

  4. css spprite应用

    (一)实现简单的淘宝带图标侧边栏效果 <!DOCTYPE html> <html lang="en"> <head> <meta char ...

  5. java&period;lang&period;NoClassDefFoundError&colon; javax&sol;servlet&sol;ServletContext

    方法1:把SpringBoot中main方法所在的class不再继承org.springframework.boot.context.web.SpringBootServletInitializer即 ...

  6. 【Oracle】虚拟表Dual

    Dual是个虚拟表,用来构成SELECT语句的语法规则,Oracle保证Dual里面永远只有一条记录.可以用它来做很多事情,例如,查看当前用户:用来调用系统函数:得到序列的下一个值或者当前值:可以用作 ...

  7. cesium加载纽约市3dtiles模型

    const tileset = new Cesium.Cesium3DTileset({ url: '../../assets/data/NewYork/tileset.json' }); viewe ...

  8. PHP数组——数组正则表达式、数组、预定义数组

    正则表达式 1.替换 $s = "hello5world"; $s = preg_replace("/\d/","#",$s); echo ...

  9. vue修改框架样式&sol;deep&sol;

    /deep/ 父元素的样式名 /deep/ 要修改的样式名 使用 ... 貌似不行

  10. D5 LCA 最近公共祖先

    第一题: POJ 1330 Nearest Common Ancestors POJ 1330 这个题可不是以1为根节点,不看题就会一直wa呀: 加一个找根节点的措施: #include<alg ...