AcWing 000. n皇后问题-斜率
原题链接
简单
作者:
CqAq
,
2024-04-10 16:30:23
,
所有人可见
,
阅读 6
算法1
C++ 代码
#include <bits/stdc++.h> ///N皇后问题
using namespace std;
int n, mp[15], ans;
bool check(int row, int col){
for(int i = 1; i < row; ++i){
if(mp[i] == col) return false;
if(abs(row-i) == abs(col-mp[i])) return false; ///一次函数斜率采用消去分母后相等的方法,避免除法
//if(row-i == mp[i]-col) return false;
}///不用枚举判断同一行,因为row每次都是向下递归,不会重复
return true;
}
void dfs(int row){///以行做dfs
if(row == n + 1){
ans ++;
return ;
}
for(int col = 1; col <= n; ++ col){//枚举每一列再dfs
if(check(row, col)){//符合条件
mp[row] = col;//------------------------------->>>>>以行为下标,值为列--经典声明数组
dfs(row+1);
mp[row] = 0;
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans;
return 0;
}
算法2
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n, mp[15], ans;
bool check(int row, int col){
for(int i = 1; i < row; ++i){
if(mp[i] == col) return false;
if(row-i == col-mp[i]) return false;
if(row-i == mp[i]-col) return false;
}
return true;
}
void dfs(int row){
if(row == n + 1){
ans ++;
return ;
}
for(int col = 1; col <= n; ++ col){ ///枚举列
if(check(row, col)){ ///对应的列,赋值给行
mp[row] = col;
dfs(row+1);
mp[row] = 0;
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans;
return 0;
}