题目
在8×8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后,这就是一种符合条件的摆放方法。请求出总共有多少种摆法。
思路
这就是有名的八皇后问题。解决这个问题通常需要用递归,而递归对编程能力的要求比较高。因此有不少面试官青睐这个题目,用来考察应聘者的分析复杂问题的能力以及编程的能力。
由于八个皇后的任意两个不能处在同一行,那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组colIndex[8],colIndex[i]表示位于第i行的皇后的列号。先把colIndex的八个数字分别用0-7初始化,接下来我们要做的事情就是对数组colIndex做全排列。由于我们是用不同的数字初始化数组中的数字,因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上,也就是数组的两个下标i和j,是不是i-j==colIndex[i]-colIndex[j]或者j-i==colIndex[i]-colIndex[j]。
关于全排列问题参考:[LeetCode]46.Permutations
代码
#include <iostream>
#include <vector>
using namespace std;
bool Check(vector<int> colIndex,int n){
bool a,b;
for(int i = 0;i < n;++i){
for(int j = i+1;j < n;++j){
a = (i - j == colIndex[i] - colIndex[j]);
b = (j - i == colIndex[i] - colIndex[j]);
if(a || b){
return false;
}
}
}
return true;
}
void Permutation(vector<int> &colIndex,int n,int index,int &count,vector<bool> &visited){
if(index == n){
if(Check(colIndex,n)){
++count;
for(int i = 0;i < n;++i){
cout<<colIndex[i]<<" ";
}
cout<<endl;
}
return;
}
for(int i = 0;i < n;++i){
if(!visited[i]){
colIndex[index] = i;
visited[i] = true;
Permutation(colIndex,n,index+1,count,visited);
visited[i] = false;
}
}
}
int EightQueen(){
int count = 0;
int n = 8;
vector<int> colIndex(n,0);
vector<bool> visited(n,false);
Permutation(colIndex,n,0,count,visited);
return count;
}
int main(){
cout<<EightQueen()<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
程序员面试题精选100题
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
程序员面试题精选100题
程序员面试题精选100题完整版.pdf,这是一份不错的文件
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试试题.txt程序员面试试题.txt程序员面试试题.txt程序员面试试题.txt
程序员面试题精选100题
------------------------------------- java程序员早期面试题汇总 BAT经典面试题汇总.pdf Java常考面试题.pdf java面试题(题库全)....程序员面试题精选100题.pdf ... -------------------------------------
程序员面试题精选100题(2008)程序员面试题精选100题(2008)
程序员面试题精选100例.doc
程序员面试题精选100题