- 浏览: 35940 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1753 Accepted Submission(s): 769
Problem Description
在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。
你的任务是,对于给定的N,求出有多少种合法的放置方法。
Input
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。
Sample Input
1 8 5 0
Sample Output
1 92 10
Author
cgf
Source
Recommend
lcy
经典问题,不过注意预处理之后先上交,唔系会超时{= =}
贴代码:
4286478 | 2011-07-29 14:21:12 | Accepted | 2553 | 31MS | 240K | 1060 B | C++ | 10SGetEternal{(。)(。)}! |
#include <iostream> using namespace std; #define MAXI 11 int maz[MAXI][MAXI]; void mark(int n, int x, int y, int add) { int i, f = 1; for (i = 0;f ; i++) { f = 0; if (x - i >= 0 || y - i >= 0 || x + i < n || y + i < n) { f = 1; if (x + i < n) maz[x + i][y] += add; if (y + i < n) maz[x][y + i] += add; if (x - i >= 0) maz[x - i][y] += add; if (y - i >= 0) maz[x][y - i] += add; if (x + i < n && y + i < n) maz[x + i][y + i] += add; if (x + i < n && y - i >= 0) maz[x + i][y - i] += add; if (x - i >= 0 && y + i < n) maz[x - i][y + i] += add; if (x - i >= 0 && y - i >= 0) maz[x - i][y - i] += add; } } } int DFS(int x, int n) { int y, tsu = 0; if (x == n) return 1; for (y = 0; y < n; y++) if (!maz[x][y]) { mark(n, x, y, 1); tsu += DFS(x + 1, n); mark(n, x, y, -1); } return tsu; } int main() { int n, i, step[MAXI]; for (i = 0; i < MAXI; i++) step[i] = DFS(0, i); while (scanf("%d", &n), n) printf("%d\n", step[n]); return 0; }
水题也……
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1149Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 832What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1169Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 765find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 994Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 733box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 784Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 968Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1160二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 984Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 861Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 767Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1013分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1227Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1069Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 638Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 569find the safest road Time Limi ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 756Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 640开门人和关门人 Time Limit: 2000/1000 ... -
HDU 1316 How Many Fibs? .
2011-07-31 20:15 941How Many Fibs? Time Limit: 200 ...
相关推荐
HDU 里面的2000~2099道题目的源码。谢谢支持
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
杭电acm 一些java语言实现的水题目
杭电ACM2000-2099题的解题报告
杭电选课插件
HDU的一题........HDU DP动态规
ACM HDU题目分类,我自己总结的大概只有十来个吧
算术(HDU-6715).rar
算法-数塔(HDU-2084).rar
杭电操作系统实验 HDU操作系统实验.zip
最短路(HDU-2544).rar