八皇后问题的变形，也不能说是变形，叫做改了一下下
问题描述
地球人都知道，在国际象棋中，后如同太阳，光芒四射，威风八面，它能控制横、坚、斜线位置。
看过清宫戏的中国人都知道，后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围，但也总能找到相安无事的办法。
所有中国人都知道，皇权神圣，伴君如伴虎，触龙颜者死…
现在有一个n*n的皇宫，国王占据他所在位置及周围的共9个格子，这些格子皇后不能使用（如果国王在王宫的边上，占用的格子可能不到9个）。当然，皇后也不会攻击国王。
现在知道了国王的位置（x,y）（国王位于第x行第y列，x,y的起始行和列为1），请问，有多少种方案放置n个皇后，使她们不能互相攻击。输入格式
一行，三个整数，皇宫的规模及表示国王的位置
输出格式
一个整数，表示放置n个皇后的方案数
样例输入
8 2 2
样例输出
10
数据规模和约定
n<=12
就是多了一个皇上，地图上多几个点不能放而已，标记出来就行了，
#include#include using namespace std; //hou数组表示的意思:hou[i] 表示第i行放的皇后在第hou[i]列 //例如：hou[1] = 2, 表示第一行皇后放在第二列 int n, x, y, ans = 0, hou[15]; //地图，用标记指明皇上所待的位置以及它周边位置 bool map[15][15]; //皇上的上，左上，左，左下，下，右下，右，右上 int direct[9][2] = { {-1,0},{-1,-1},{0,-1},{1,-1}, {1,0},{1,1},{0,1},{-1,1} }; //表示正在试探第row行放皇后 void dfs( int row); //主函数 int main() { cin >> n >> x >> y; //标记 map[x][y] = true; for ( int i = 0; i < 9; ++i ) { int tx = x + direct[i][0]; int ty = y + direct[i][1]; if ( tx >= 1 && tx <= n && ty >= 1 && ty <= n ) { map[tx][ty] = true; } } dfs(1); cout << ans << endl; return 0; } void dfs( int row ) { //前面n行放完了，就表示放好了 if ( row > n ) { ans++; return ; } //每一行有n个位置，我们一个个来考虑 for ( int i = 1; i <= n; ++i ) { //判断位置是否合法 if ( !map[row][i] ) { bool flag = true; for ( int j = 1; j < row; ++j ) { if ( abs(row - j) == abs(i - hou[j]) || i == hou[j] ) { flag = false; break; } } if ( flag ) { hou[row] = i; dfs(row+1); } } } }
有可能有的同学对八皇后不熟悉，我下面简明说一说n皇后问题（其实n皇后跟八皇后思路差不多），
这个皇后的规则就是每个皇后都能攻击她所在的行，列，左斜线，右斜线的所有位置，所以我们就要让每个皇后都避开其余皇后的攻击范围。
以四皇后举例子：
这其实就是一个枚举的思路，我们对每一行的每个点进行尝试，如果合法就放下，不合法就尝试这一列的下一个点
第一行就放下了，看第二行：
根据规则，上面的红色皇后攻击范围如上图，所以绿色的点不能放，所以我们第二行暂时放在第三列：
后面的步骤都是类似的：
怎么判断两个皇后能不能打架呢？
举个例子：每行只能放一个皇后这是毋庸置疑的，所以如果
1.列相同，那必定打架；
再来说斜线的情况：假如皇后在(1,1),那么她的右斜线坐标依次是(2,2),(3,3)…
假如皇后在(1,2), 那么她的右斜线攻击坐标(2,3),(3,4)…
想不清楚，多举几个例子，
- 对角线的情况 ：abs(行-行) == abs(列 - 列) ，那么这俩心机婊就要开始撕逼了。abs表示绝对值
#include#include using namespace std; //hou数组表示的意思:hou[i] 表示第i行放的皇后在第hou[i]列 //例如：hou[1] = 2, 表示第一行皇后放在第二列 int n, x, y, ans = 0, hou[15]; //表示正在试探第row行放皇后 void dfs( int row); //主函数 int main() { cin >> n; dfs(1); cout << ans << endl; return 0; } void dfs( int row ) { //前面n行放完了，就表示放好了 if ( row > n ) { ans++; for ( int i = 1; i <= n; ++i ) { for ( int j = 1; j <= n; ++j ) { if ( j == hou[i] ) cout << "Q"; else cout << "#"; } cout << endl; } cout << endl; return ; } //每一行有n个位置，我们一个个来考虑 for ( int i = 1; i <= n; ++i ) { //判断位置是否合法 bool flag = true; //放第row行，我们就要看看跟前面已经放好的有没有冲突 //前面就是1~~(row-1)行嘛 for ( int j = 1; j < row; ++j ) { if ( abs(row - j) == abs(i - hou[j]) || i == hou[j] ) { flag = false; break; } } if ( flag ) { hou[row] = i; //放位置 dfs(row+1); } } }
