注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex52 N-Queens II  

2015-05-25 22:10:57|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

ex52 N-Queens II - HT - HT·生活


就是要输出可行解的个数,这就更简单了,把ex51改动一下就可以了,连字符串都不需要构造了,非递归的和这个几乎一样。

/*
* 输出解的个数,这就比上一个题ex51简单多了
*/
class Solution {
public:
int result;
int totalNQueens(int n) {
result = 0;
if (n <= 0)
return result;
vector<int>queen(n, -1);//棋盘中所有的元素都存-1
int index = 0;
traverse(queen, index);
return result;
}
void traverse(vector<int>&queen, int index)
{
//queen[i]表示第i行 皇后的位置
int len = queen.size();
int i = 0;
//index表示现在该存第几个皇后到了
if ((index + 1) == len)
{
//退出条件是最后一个皇后是否能够放置
bool mark = false;
for (i = 0; i < len; i++)
{
if (!conflict(queen, index, i))
{
//找到答案了
queen[index] = i;
result++;
break;
}
}
}
else
{
bool mark = false;
for (i = 0; i < len; i++)
{
mark = conflict(queen, index, i);
if (!mark)
{
queen[index] = i; //第index行的Q放在 i列上
traverse(queen, index + 1); //遍历下一个皇后的位置
}
}
}
}
bool conflict(vector<int>queen, int index, int col)
{
//index表示的行
//col 表示的是列
//判定如果第index行放在第col列是否冲突
int i = 0;
int dis1, dis2, dis3, dis4;
for (i = 0; i <index; i++)
{
//擦,开始的时候判定规则写错了,恶心死我了
//注释里面的一个一个正确的规则
//dis1 = i - queen[i];
//dis2 = index - col;
//dis3 = i + queen[i];
//dis4 = index + col;
//if (dis2 == dis1||col==queen[i]||dis3==dis4)
// return true;
dis1 = abs(i - index);
dis2 = abs(queen[i] - col);

if (dis2 == dis1 || col == queen[i])
return true;
}
return false;
}
};



  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017