蓝桥杯王、后传说 dfs

问题描述

　　地球人都知道，在国际象棋中，后如同太阳，光芒四射，威风八面，它能控制横、坚、斜线位置。
　　看过清宫戏的中国人都知道，后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围，但也总能找到相安无事的办法。
　　所有中国人都知道，皇权神圣，伴君如伴虎，触龙颜者死......
　　现在有一个n*n的皇宫，国王占据他所在位置及周围的共9个格子，这些格子皇后不能使用（如果国王在王宫的边上，占用的格子可能不到9个）。当然，皇后也不会攻击国王。
　　现在知道了国王的位置（x,y）（国王位于第x行第y列，x,y的起始行和列为1），请问，有多少种方案放置n个皇后，使她们不能互相攻击。

输入格式

　　一行，三个整数，皇宫的规模及表示国王的位置

输出格式

　　一个整数，表示放置n个皇后的方案数

样例输入

8 2 2

样例输出

数据规模和约定

　　n<=12

最基本的n皇后问题我又忘记怎么做了，复习复习复习复习。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int ans; //答案 
 4 int n; //棋盘规模 
 5 int mp[20][20]; //棋盘 
 6 bool col[15], x1[30], x2[30]; // 标识列和两条对角线
 7 bool check(int r, int i) { //检查第r行第i列是否可以放 
 8     if (!col[i] && !x1[r + i] && !x2[r - i + 12]) { //这一点所在的列，所在的左对角线，所在的右对角线没放过 
 9         return true;
10     }
11     return false;
12 } 
13 void init(int a, int b) { //国王所在的9个方格不能放，标识为1 
14     mp[a - 1][b - 1] = 1, mp[a - 1][b] = 1, mp[a - 1][b + 1] = 1, mp[a][b -1] = 1;
15     mp[a][b] = 1, mp[a][b + 1] = 1, mp[a + 1][b - 1] = 1, mp[a + 1][b] = 1;
16     mp[a + 1][b + 1] = 1;
17 }
18 void dfs(int r) { // 搜索到第r行
19     if (r == n + 1) { //搜索完了 
20         ans++;
21         return;
22     } 
23     for (int i = 1; i <= n; i++) { //遍历所有列 
24         if (check(r, i) && mp[r][i] != 1) { // 如果r行i列可以放 
25             col[i] = x1[r + i] = x2[r - i + 12] = true; // i列，r + i对角线，r - i对角线标记一下 
26             dfs(r + 1); // 进入下一行 
27             col[i] = x1[r + i] = x2[r - i + 12] = false; //回溯,取消标记 
28         }
29     }
30 }
31 int main() {
32     int a, b;
33     cin >> n >> a >> b;
34     init(a, b); //处理国王的9个格子 
35     dfs(1); //从第一行开始搜索 
36     cout << ans << endl;
37     return 0;
38 }

蓝桥杯 王、后传说 dfs

蓝桥杯王、后传说 dfs