698 . 除草機

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-enumerate

Description

在一塊 $N\times N$ 的土地上，有些格子上有雜草。一個偷懶的園丁想要方便的除草，他發現一台直直開過的除草機可以將一整行或一整列的雜草消除，然而除草機不能斜著開。想請問你在給定雜草的位置下，最少要發動幾次除草機才能把雜草清光？

Input Format

輸入第一行是一個正整數 $N$，表示土地大小。
接著有 $N$ 行，第 $i$ 行有 $N$ 個空白分隔的數字 $a_{ij} (1\le i, j\le N)$，當 $a_{ij} = 1$ 時表示第 $i$ 列第 $j$ 行的位置有雜草，當 $a_{ij} = 0$ 時表示上述位置沒有雜草。

輸入保證 $1\le N\le 20$，$0\le a_{ij}\le 1$。
其中對於 $40\%$ 的測資，額外保證 $1\le N\le 10$。

Output Format

本題必須輸出最少次數並給出一個例子。

第一行輸出一個正整數 $m$ 表示最少發動除草機次數。
第二行輸出 $N$ 個 $0$ 或 $1$ 的數字，數字間以空白分隔，第 $i$ 個數字是 $1$ 表示第 $i$ 列要發動除草機，$0$ 表示不發動除草機。
第三行輸出 $N$ 個 $0$ 或 $1$ 的數字，數字間以空白分隔，第 $i$ 個數字是 $1$ 表示第 $i$ 行要發動除草機，$0$ 表示不發動除草機。

Sample Input 1

2
1 0
0 1

Sample Output 1

2
0 0
1 1

Sample Input 2

3
1 0 0
0 1 1
1 0 0

Sample Output 2

2
0 1 0
1 0 0

Hints

Problem Source

TOI 2021 初選

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13 $N\le 10$ 40
3 0~24 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 2 3
12 1000 524288 65536 2 3
13 1000 524288 65536 2 3
14 1000 524288 65536 3
15 1000 524288 65536 3
16 1000 524288 65536 3
17 1000 524288 65536 3
18 1000 524288 65536 3
19 1000 524288 65536 3
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
Submit
Back to Top