蓝桥杯算法训练VIP-王、后传说 （C++代码）

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