解题思路:很经典的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分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论