中山建网站,推广方法,长沙广告网络公司,wordpress弹出搜索题目描述
给出一个nnn\times nnn的国际象棋棋盘#xff0c;你需要在棋盘中摆放nnn个皇后#xff0c;使得任意两个皇后之间不能互相攻击。具体来说#xff0c;不能存在两个皇后位于同一行、同一列#xff0c;或者同一对角线。请问共有多少种摆放方式满足条件。
输入描述: …
题目描述
给出一个n×nn\times nn×n的国际象棋棋盘你需要在棋盘中摆放nnn个皇后使得任意两个皇后之间不能互相攻击。具体来说不能存在两个皇后位于同一行、同一列或者同一对角线。请问共有多少种摆放方式满足条件。
输入描述:
一行一个整数n(1≤n≤12)n(1\le n \le 12)n(1≤n≤12)表示棋盘的大小。
输出描述:
输出一行一个整数表示总共有多少种摆放皇后的方案使得它们两两不能互相攻击。
示例1
输入
4
输出
2
想法
就按题意一个格子一个格子枚举并看一下有没有行冲突列冲突对角线冲突但结果答案是错的。
代码
#includebits/stdc.h using namespace std; int n; int ans0; int a[15][15]; int st[15][15]; int r[15];//行冲突 int c[15];//列冲突 int djx[2];//对角线冲突 void dfs(int gs){//摆了的皇后个数 //st[x][y]1; if(gsn){ ans; return ; } for(int i1;in;i){ for(int j1;jn;j){ //if(st[i][j]) break; if(r[i]) break; if(c[j]) continue; if(djx[0]ij) continue; if(djx[1]ijn1) continue; r[i]1; c[j]1; if(ij){ djx[0]1; dfs(gs1); djx[0]0; } else if(ijn1){ djx[1]1; dfs(gs1); djx[1]0; } else dfs(gs1); r[i]0; c[j]0; } } } int main(){ cinn; dfs(0); coutans; }
网课
看了网课后发现还是有点问题的吧。首先对角线冲突理解错了题目指的是每条对角线而我以为是主对角线和副对角线两条。然后我又想了下怎么标记对角线找了下对角线的下标有什么规律emm但也还是想不到怎么表示。网课的提供了两种方法一种是直接将所有对角线标序号然后弄个标记数组第二种就是看规律主对角线方向上的位于同一条对角线的坐标ij都是同一个值副对角线方向上的位于同一条对角线的坐标i-j都是同一个值。利用这点可以弄两个标记数组。但还有问题就是副对角线方向上的某些对角线坐标相减是负的需要把数组下标平移一下。我找规律的时候也有注意到一点点吧但没那么深刻。还有一点就是网课的方法搜索时是一行一行搜的每一行放一个皇后看是否满足条件这样直接不用考虑行冲突了。我是一格一格搜索的复杂度更高。
代码
#includebits/stdc.h using namespace std; const int N15; int n; int ans0; int c[N]; int fdjx[NN-1N];//平移 int zdjx[NN-1]; void dfs(int r){//行 if(rn){ ans; return ; } for(int i1;in;i){//列 if(c[i]) continue; if(fdjx[r-in]) continue; if(zdjx[ri]) continue; c[i]1; fdjx[r-in]1; zdjx[ri]1; dfs(r1); c[i]0; fdjx[r-in]0; zdjx[ri]0; } } int main(){ cinn; dfs(1); coutans; }
修改
但是吧我现在按我的想法写就是一格一格搜索还是弄不出来。
代码
#includebits/stdc.h using namespace std; const int N15; int n; int ans0; int c[N]; int r[N]; int fdjx[NN-1N];//平移 int zdjx[NN-1]; void dfs(int gs){//行 if(gsn){ ans; return ; } for(int i1;in;i){//列 for(int j1;jn;j){ if(c[j]) continue; if(r[i]) break; if(fdjx[i-jn]) continue; if(zdjx[ij]) continue; c[j]1; r[i]1; fdjx[i-jn]1; zdjx[ji]1; dfs(gs1); c[i]0; r[i]0; fdjx[i-jn]0; zdjx[ji]0; } } } int main(){ cinn; dfs(1); coutans; }
