Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5382 Accepted Submission(s): 2454
Problem Description 在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。Input 共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output 共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input 1 8 5 0
Sample Output 1 92 10
Author cgf
Source 2008 HZNU Programming Contest
经典dfs
#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; int ch[25][25]; // 棋盘int n, num, result[25]; void dfs(int x, int y) { if(ch[x][y]) return; //如果该点已经被攻击，则返回 int i, xx, yy; if(x == n) //如果 { num++; return; } //下面个人觉得比较巧妙，因为会有重复的地方很难分析是属于哪个皇后 //若用了下面位置的 ++ or -- ，则巧妙地避免上述情况 //一共八个方向进行标记：上、下、左、右、左上、左下、右上、右下 xx = x; yy = y; while(xx>0) ch[xx--][y]++; xx = x; yy = y; while(yy>0) ch[x][yy--]++; xx = x; yy = y; while(xx<=n) ch[xx++][y]++; xx = x; yy = y; while(yy<=n) ch[x][yy++]++; xx = x; yy = y; while(xx<=n && yy<=n) ch[xx++][yy++]++; xx = x; yy = y; while(xx>0 && yy<=n) ch[xx--][yy++]++; xx = x; yy = y; while(xx<=n && yy>0) ch[xx++][yy--]++; xx = x; yy = y; while(xx>0 && yy>0) ch[xx--][yy--]++; for(i = 1; i <= n; i++) { dfs(x+1, i); } //若这个皇后深搜后的结果不成功，则要返回原来的情况，八个方向都 -- xx = x; yy = y; while(xx>0) ch[xx--][y]--; xx = x; yy = y; while(yy>0) ch[x][yy--]--; xx = x; yy = y; while(xx<=n) ch[xx++][y]--; xx = x; yy = y; while(yy<=n) ch[x][yy++]--; xx = x; yy = y; while(xx<=n && yy<=n) ch[xx++][yy++]--; xx = x; yy = y; while(xx>0 && yy<=n) ch[xx--][yy++]--; xx = x; yy = y; while(xx<=n && yy>0) ch[xx++][yy--]--; xx = x; yy = y; while(xx>0 && yy>0) ch[xx--][yy--]--; } void init() //初始化函数 { int i, j; for(i = 0; i < 12; i++) for(j = 0; j < 12; j++) ch[i][j] = 0; } void set() { int i, k; init(); for(k = 1; k <= 10; k++) { num = 0; n = k; //初始化 for(i = 1; i <= k; i++) { //初始化 dfs(1, i); //继续dfs寻找 } result[k] = num; } } int main() { set(); while(scanf("%d", &n), n) { int a=result[n]; printf("%d\n", a); } return 0; }
转载于:https://www.cnblogs.com/Skyxj/p/3180930.html
