691 . K皇后

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

joycewang

User's AC Ratio

92.3% (12/13)

Submission's AC Ratio

38.5% (15/39)

Tags

apcsc apcsc-enumerate

Description

在一個 $N \times N$ 的西洋棋棋盤上有 $N$ 個皇后，每個皇后都佔據一個格子而攻擊範圍同標準西洋棋規則，國王希望他們互相不能攻擊，請列出所有可能的皇后擺放位置。

皇后攻擊範圍如下：

Input Format

輸入只有一行，包含一個正整數 $1 \le N \le 12$ 代表棋盤的大小。

Output Format

輸出總共有 $(N+1)\cdot S$ 行，其中 $S$ 是皇后擺放方式的數量。

一個皇后擺放方式可以表示成一個長度 $N$ 的序列 $(A_1, A_2, \cdots, A_N)$ ，代表第 $i$ 個橫列的皇后放在第 $A_i$ 直行。這 $S$ 個解請照序列的字典序由小到大輸出，換句話說，第一橫列的皇后放在第一直行的解會優先輸出，而第一橫列的皇后放在最後一直行的解則會最後輸出。

對於每一個皇后擺放方式，輸出 $(N+1)$ 行長度為 $N$ 的字串，如果棋盤的第 $i$ 橫列第 $j$ 直行是一個皇后，則在第 $i$ 行的第 $j$ 個字元輸出 Q，否則輸出 *，最後一行則是一個空行。

請注意如果沒有合法的皇后擺放方式，輸出將會是空的，另外，如果有解的話，最後一行一定是空行（所以輸出格式比較方便 :p）。

Sample Input 1

4

Sample Output 1

*Q**
***Q
Q***
**Q*

**Q*
Q***
***Q
*Q**

Sample Input 2

2

Sample Output 2

Hints

Problem Source

經典題

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
Submit
Back to Top