直播是网站怎么做,网站编程教学,公众号微网站制作,海拉尔做网站多少钱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
解题思路 这题我们用了
if (!col[y] !duijiao1[x y] !duijiao2[x - y n])进行剪枝但是没用还是超时所以我们要用打表的方法在main()中提取算好答案然后存储在数组中等读取输入后立刻输出而不是等输入了n在慢慢计算会超时。
代码如下
#include iostream
#include cstring
using namespace std;
int ans 0;
int n;
const int N 1010;
bool col[N], duijiao1[N], duijiao2[N];void dfs(int x) {if (x n) {ans;return ;}for (int y 1; y n; y) {if (!col[y] !duijiao1[x y] !duijiao2[x - y n]) {col[y] duijiao1[x y] duijiao2[x - y n] true;dfs(x 1);col[y] duijiao1[x y] duijiao2[x - y n] false;}}
}int main() {while (cin n, n) {memset(col, 0, sizeof(col));memset(duijiao1, 0, sizeof(duijiao1));memset(duijiao2, 0, sizeof(duijiao2));ans 0;dfs(1);cout ans endl;}return 0;
}打表大法
#include iostream
#include cstring
using namespace std;
int ans 0;
int n;
const int N 1010;
bool col[N], duijiao1[N], duijiao2[N];
int biao[15];void dfs(int x) {if (x n) {ans;return ;}for (int y 1; y n; y) {if (!col[y] !duijiao1[x y] !duijiao2[x - y n]) {col[y] duijiao1[x y] duijiao2[x - y n] true;dfs(x 1);col[y] duijiao1[x y] duijiao2[x - y n] false;}}
}int main() {for ( n 1; n 10; n) {ans 0;memset(col, 0, sizeof(col));memset(duijiao1, 0, sizeof(duijiao1));memset(duijiao2, 0, sizeof(duijiao2));dfs(1);biao[n] ans;}while (cin n, n) {cout biao[n] endl;}return 0;
}
