698 . 除草機

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

64.3% (9/14)

Tags

apcsc apcsc-enumerate

Description

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

Input Format

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

輸入保證 1≤N≤20，0≤aij≤1。
其中對於 40% 的測資，額外保證 1≤N≤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≤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