赞
踩
前置知识:
根据数学函数 y = x +b;
当不同的一元函数的斜率相同时,唯一能区分他们的就是截距b
因此,可以由 b = y-x 得到不同的对角线直线函数(我们假设这些直线的斜率都是1)
那么反对角线 y = -x +b 所以b = x+y;
正对角线 b = y-x
可能出现b<0 的情况,所以我们给b加一个数当偏移量c,至于这个数是多少无所谓,只要保证这个数 c+y-x>0即可
其实b是多少不重要,重要的是我们能用b来唯一确定这条对角线,作为一个唯一表示,来映射出这条直线
整体思路:
全排列思想
因为每一行只能放一个皇后,只要当这一行出现过皇后,那就进入下一行
所以我们可以遍历每一行的所有列,只要在这个点放了皇后,那么直接进入下一行
#include<iostream> int n; char q[20][20]; bool f[100],zh[100],fn[100]; void dfs(int u){ //已经遍历完了所有的行,输出答案 if(u>n){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)std::cout<<q[i][j]; std::cout<<std::endl; } std::cout<<std::endl; return ; } for(int i=1;i<=n;i++){ //f里面装的是这一列是否已经用过 //有这三个判断在,只有满足题意的皇后能走到最后一层 //不符合题意的提前剪枝了 if(!f[i]&&!zh[i+u]&&!fn[n+u-i]){ f[i] = zh[i+u] = fn[n+u-i] = true; q[u][i] = 'Q'; dfs(u+1);//进入下一层 f[i] = zh[i+u] = fn[n+u-i] = false; q[u][i] = '.'; } } } int main(){ std::cin>>n; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)q[i][j] = '.'; dfs(1); return 0; }
思路:
暴力遍历每一个格子是否能填皇后,所以有两种情况,填和不填
用数组剪枝一下,填的时候还要注意得能填,不能填的位置不能填,实现剪枝的效果
能填的情况:这一行,这一列,这一正对角线,这一反对角线都无皇后
#include<iostream> const int N=100; int n; bool row[N],col[N],pl[N],inv[N];//行,列,正对角线,反对角线 char q[N][N]; void dfs(int x,int y,int num){ //num当前已经有多少八皇后存进去了 if(y>n)y = 1,x++; if(x>n){ if(num==n){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)std::cout<<q[i][j]; std::cout<<std::endl; } std::cout<<std::endl; } return ; } //不填八皇后 dfs(x,y+1,num); if(!row[x]&&!col[y]&&!pl[x+y]&&!inv[n+y-x]){ row[x] = col[y] = pl[x+y] = inv[n+y-x] = true; q[x][y] = 'Q'; //因为这一行填了皇后,进入下一行就要从第一列开始判断 //num可以写在传参也可以写在外面 //例如 num++; dfs(x+1,1);num--; //记得恢复现场就行 dfs(x+1,1,num+1); row[x] = col[y] = pl[x+y] = inv[n+y-x] = false; q[x][y] = '.'; } } int main(){ std::cin>>n; for(int i=1;i<=n;i++)for(int j = 1;j<=n ;j++)q[i][j] = '.'; dfs(1,1,0); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。