641 . 皇后-PLUS

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

33.3% (1/3)

Tags

apcsc apcsc-review

Description

$N$ 皇后是一個經典的演算法問題，給定一個 $N\times N$ 的西洋棋棋盤，要將 $N$ 個皇后擺放在西洋棋盤上，並使得這 $N$ 個皇后不會互相攻擊。已知皇后可以在直線與斜線方向移動任意的步數，若西洋棋的規則新增一個新的角色「皇后 - PLUS」，其攻擊範圍與皇后相同，外加可以移動到以「皇后 - PLUS」為中心的 $5\times 5$ 格子中。

請你寫一個程式解出 $N$ 皇后 - PLUS 的題目：將 $N$ 個「皇后 - PLUS」放在 $N\times N$ 的西洋棋棋盤上，使得這 $N$ 個「皇后 - PLUS」不會互相攻擊。若存在多組可能的放法，請輸出任意一組放法即可；若沒有可以在 $N\times N$ 的棋盤上放 $N$ 個「皇后 - PLUS」的解，請輸出 QQ。

Input Format

輸入只有一個數字 $N$（$1 \le N \le 20$），代表棋盤的大小及要放上去的「皇后 - PLUS」數量。

Output Format

若此 $N$「皇后 - PLUS」問題有解，請輸出 $N$ 行，每行共有 $N$ 個以空白分隔的 0 或 1，1 代表該格有放皇后、0 代表該格為空。若此 $N$「皇后 - PLUS」問題無解，請輸出字串 QQ。

Sample Input 1

2

Sample Output 1

QQ

Sample Input 2

12

Sample Output 2

0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~21 無額外限制 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
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
Submit
Back to Top