身為考古學家的你,拿到了一份上古年代的黑白文件,為了方便閱讀,你必須先對這份文件進行修復,修復的考慮如下:
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$。
請注意,這個修復為用來解釋成本計算,不一定代表這份文件的最佳解。
輸入第一行有兩個正整數 $N,M(1 \leq N\cdot M \leq 20)$。
之後有 $N$ 行,每行有 $M$ 個 $0$ 或 $1$ 的數字用來描述原本的文件。
請輸出一個整數,代表修復這份文件的最小成本。
TOI2019 初選 pE subtask1
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~20 | 無額外限制 | 100 |