798 . 黑白巧克力
TopCoder
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
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
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 |