Pro.ID21729 TitleQUEEN KINGDOM Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21729 AC0 Submit0 Ratio- 时间&空间限制描述A game designer wants to build a modified chess board of size n by n. At certain squares there will be placed pillars that prevent placement of pieces and also prevent attacks across them. Before shipping the specifications to a manufacturer, the designer wants to know what is the maximum number of non-attacking queens that can be placed on each of his designs. Recall that queens can attack vertically, horizontally and diagonally as far as possible until the end of board (or, in our case, until a pillar is reached). Also of interest is how many different ways this maximum number can be achieved. 输入Input consists of scenarios. Each scenario starts with an integer n (n <= 10). Input ends when n = 0. The next n lines, each containing n characters represent the rows of the chess board. Here, a '0' represents and open square and a '1' represents a pillar. 输出Description A game designer wants to build a modified chess board of size n by n. At certain squares there will be placed pillars that prevent placement of pieces and also prevent attacks across them. Before shipping the specifications to a manufacturer, the designer wants to know what is the maximum number of non-attacking queens that can be placed on each of his designs. Recall that queens can attack vertically, horizontally and diagonally as far as possible until the end of board (or, in our case, until a pillar is reached). Also of interest is how many different ways this maximum number can be achieved. Input Input consists of scenarios. Each scenario starts with an integer n (n <= 10). Input ends when n = 0. The next n lines, each containing n characters represent the rows of the chess board. Here, a '0' represents and open square and a '1' represents a pillar. Output For each case output the maximum number queens that can be placed, followed by the number of different ways possible (separated by a single space). Sample Input 3
010
111
000
6
000000
000000
000000
000000
000000
000000
6
000010
001110
111011
010110
011010
010010
0 Sample Output 3 3
6 4
7 270 Source 样例输入3
010
111
000
6
000000
000000
000000
000000
000000
000000
6
000010
001110
111011
010110
011010
010010
0 样例输出3 3
6 4
7 270 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 18:02 , Processed in 0.035201 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
