TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

身為考古學家的你,拿到了一份上古年代的黑白文件,為了方便閱讀,你必須先對這份文件進行修復,修復的考慮如下:
1. 修復後的文件需盡量與原本相同
2. 為了閱讀的美觀,相鄰位置的顏色需盡量相同

綜合上述,你可以定義出修復後的文件成本如下:
1. 若某個位置修復後的顏色與原本不同,這個位置的成本為 $2$
2. 若某組相鄰位置的顏色不同(相鄰的定義為有共邊即上下左右),則這組相鄰位置的成本為 $1$

舉例而言:

若一份

0 0 1
0 0 1
0 1 1

的文件被修復為

0 0 1
0 0 1
0 0 1

則此次修復成本為 $2\cdot1+1\cdot3=5$。
請注意,這個修復為用來解釋成本計算,不一定代表這份文件的最佳解。

Input Format

輸入第一行有兩個正整數 $N,M(1 \leq N\cdot M \leq 20)$。
之後有 $N$ 行,每行有 $M$ 個 $0$ 或 $1$ 的數字用來描述原本的文件。

Output Format

請輸出一個整數,代表修復這份文件的最小成本。

Sample Input 1

3 3
1 1 0
1 1 0
1 0 0

Sample Output 1

4

Sample Input 2

1 5
0 0 1 0 1

Sample Output 2

3

Hints

Problem Source

TOI2019 初選 pE subtask1

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
16 2000 524288 65536 2
17 2000 524288 65536 2
18 2000 524288 65536 2
19 2000 524288 65536 2
20 2000 524288 65536 2