解题思路:很经典的n皇后问题改版,建议去把2n皇后问题去看一看,深入的理解一下递归的运用,其做题方法跟2n皇后问题一样,只不过这个问题是先把国王在的位置统计好,初始为map数组为1,国王在的位置为0,然后就是套用2n皇后问题的模板了,应该要吃透理解
注意事项:不能使用memset函数初始化map数组,容易出错
参考代码:
#include"iostream"
#include"algorithm"
#include"stdlib.h"
#include"string.h"
#include"stdio.h"
#include"math.h"
#include"map"
#include"vector"
#include"set"
#include"math.h"
#include"functional"
#include<iomanip>
using namespace std;
const int N = 205;
const int maxn = 1e6+6;
const int inf = 999999;
int ma[N][N];
int whit[N];
int sum = 0;
int n;
void dfs(int k)
{
for(int i = 1;i<k-1;i++)
{
int judge = whit[k-1]-whit[i];
if(judge == 0 || abs(k-1-i) == abs(judge))
return;
}
if(k == n+1)
{
sum++;
return;
}
for(int i = 1;i<=n;i++)
{
if(ma[k][i])
{
whit[k] = i;
dfs(k+1);
}
}
}
int main()
{
for(int i = 0;i<N;i++)
for(int j = 0;j<N;j++)
{
ma[i][j] = 1;
}
int x,y;
cin>>n>>x>>y;
if(x == 1 && y == 1)
{
ma[1][1] = 0;
ma[1][2] = 0;
ma[2][1] = 0;
ma[2][2] = 0;
}else if(x == 1 && y!=1 && y!=n){
ma[x][y] = 0;
ma[x][y-1] = 0;
ma[x][y+1] = 0;
ma[x+1][y] = 0;
ma[x+1][y-1] = 0;
ma[x+1][y+1] = 0;
}else if(x == 1 && y == n)
{
ma[x][n] = 0;
ma[x][n-1] = 0;
ma[x+1][n-1] = 0;
ma[x+1][n] = 0;
}else if(y == 1 && x!=1 && x!=n)
{
ma[x][y] = 0;
ma[x-1][y] = 0;
ma[x+1][y] = 0;
ma[x][y+1] = 0;
ma[x-1][y+1] = 0;
ma[x+1][y+1] = 0;
}else if(y == n && x!=1 && x!=n)
{
ma[x][y] = 0;
ma[x+1][y] = 0;
ma[x-1][y] = 0;
ma[x][y-1] = 0;
ma[x+1][y-1] = 0;
ma[x-1][y-1] = 0;
}else if(x == n && y == 1)
{
ma[x][y] = 0;
ma[x-1][y] = 0;
ma[x][y+1] = 0;
ma[x-1][y+1] = 0;
}else if(x == n && y!=1 && y!=n)
{
ma[x][y+1] = 0;
ma[x][y-1] = 0;
ma[x][y] = 0;
ma[x-1][y] = 0;
ma[x-1][y-1] = 0;
ma[x-1][y+1] = 0;
}else if(x == n && y == n)
{
ma[x][y] = 0;
ma[x-1][y] = 0;
ma[x][y-1] = 0;
ma[x-1][y-1] = 0;
}else{
ma[x][y] = 0;
ma[x-1][y] = 0;
ma[x+1][y] = 0;
ma[x][y+1] = 0;
ma[x-1][y+1] = 0;
ma[x+1][y+1] = 0;
ma[x][y-1] = 0;
ma[x-1][y-1] = 0;
ma[x+1][y-1] = 0;
}
dfs(1);
cout<<sum<<endl;
return 0;
}
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复