798 . 黑白巧克力

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-dp

Description

你有一片 $N\times M$ 的巧克力要分送給人，但是每一個小方格可能是黑巧克力也可能是白巧克力。
你每一次可以沿著邊緣剝下一條 $1\times X$ 形狀的巧克力送人，只能沿著邊緣剝而且一次必須剝下一整條。剝下來的巧克力要送人那塊不能再細分，但是如果剩下的那塊也是 $1\times X$ 的形狀則他還可以再細分。
如果要送人的巧克力有黑有白，你就必須拿黑色或白色染劑把整條染成同樣顏色。黑色染劑只需要塗在白巧克力上，同理白色染劑只需要塗在黑巧克力上。但是染劑難以取得又不健康，你希望最小化被染劑染過的巧克力格數。
請你求出在選擇適當方法剝巧克力的情況下，最少的染劑用量為何？

Input Format

輸入第一行是兩個空白分隔的整數 $N, M$，分別代表巧克力片的長寬。
接下來 $N$ 行 $M$ 個空白分隔的整數 $a_{ij} (1\le i\le N, 1\le j\le M)$ 等於 $0$ 或 $1$，$0$ 代表第 $i$ 行第 $j$ 列的那格巧克力是白色的，$1$ 代表第 $i$ 行第 $j$ 列的那格巧克力是黑色的。

輸入保證 $1\le N,M\le 25$，$0\le a_{ij}\le 1$。
其中 $30\%$ 的配分，額外滿足 $20\le N+M\le 50$。

Output Format

輸出一行一個整數，代表最少需要染幾格巧克力的顏色。

Sample Input 1

2 3
1 0 1
0 1 0

Sample Output 1

1

Sample Input 2

4 5
1 0 0 0 1
0 1 1 0 1
0 1 0 1 0
1 1 0 0 0

Sample Output 2

4

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~10 $N+M\le 13$ 30
3 0~19 無額外限制 70

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 3
12 1000 524288 65536 3
13 1000 524288 65536 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
Submit
Back to Top