698 . 除草機
TopCoder
Tags
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
1 0
0 1
Sample Output 1
2
0 0
1 1
0 0
1 1
Sample Input 2
3
1 0 0
0 1 1
1 0 0
1 0 0
0 1 1
1 0 0
Sample Output 2
2
0 1 0
1 0 0
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 |