TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

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