南阳美容网站建设,10个优秀的网页设计欣赏,哪个网站ppt模板免费下载,新塘17网站一起做网店官网Problem Description
在N*N的方格棋盘放置了N个皇后#xff0c;使得它们不相互攻击#xff08;即任意2个皇后不允许处在同一排#xff0c;同一列#xff0c;也不允许处在与棋盘边框成45角的斜线上。 你的任务是#xff0c;对于给定的N#xff0c;求出有多少种合法的放置…Problem Description
在N*N的方格棋盘放置了N个皇后使得它们不相互攻击即任意2个皇后不允许处在同一排同一列也不允许处在与棋盘边框成45角的斜线上。 你的任务是对于给定的N求出有多少种合法的放置方法。
Input 共有若干行每行一个正整数N≤10表示棋盘和皇后的数量如果N0表示结束。
Output 共有若干行每行一个正整数表示对应输入行的皇后的不同放置数量。
Sample Input 1 8 5 0
Sample Output 1 92 10
分析与解答
我们可以让皇后从第一行放到第n行我们用数组x[a]i来表示第a个皇后的位置在第a行第i列这样在每次判断是否满足情况时我们不用去判断是否皇后在相同行我们只用判断之前的1到a-1个皇后的位置和当前第a个皇后的位置是否属于同一列或者斜线判断是否同一列就判断x[a]是否等于x[i];判断是否同一斜线就判断行之差是否等于列之差也就是abs(x[k]-x[i])||x[k]x[i]。 我们写dfs如果当前皇后数量超过了n那就增加sum的个数然后停止调用如果没超过n那就要假设在第一列至第n列如果满足条件就继续调用放下一个皇后的位置main里调用dfs1 代码参考https://blog.csdn.net/u014492609/article/details/38534625
#includecstdio
#includecmath
using namespace std;
int x[15],y[15]{0};
int sum,n;
int place (int k){for(int i1;ik;i)if(abs(k-i)abs(x[k]-x[i])||x[k]x[i])return 0;return 1;
}
void dfs(int a){int i;if(an) sum;else {for(i1;in;i){x[a]i;if(place(a)) dfs(a1);}}
}
int main(){int i,j,n1;for(i1;i10;i){ni;sum0;dfs(1);y[i]sum;}while(scanf(%d,n1)1n1)printf(%d\n,y[n1]);
}
