身為考古學家的你,拿到了一份上古年代的黑白文件,為了方便閱讀,你必須先對這份文件進行修復,修復的考慮如下:
1. 修復後的文件需盡量與原本相同
2. 為了閱讀的美觀,相鄰位置的顏色需盡量相同
綜合上述,你可以定義出修復後的文件成本如下:
1. 若某個位置修復後的顏色與原本不同,這個位置的成本為
2. 若某組相鄰位置的顏色不同(相鄰的定義為有共邊即上下左右),則這組相鄰位置的成本為
舉例而言:
若一份
0 0 1
0 0 1
0 1 1
的文件被修復為
0 0 1
0 0 1
0 0 1
則此次修復成本為
請注意,這個修復為用來解釋成本計算,不一定代表這份文件的最佳解。
輸入第一行有兩個正整數
之後有
請輸出一個整數,代表修復這份文件的最小成本。
3 3 1 1 0 1 1 0 1 0 0
4
1 5 0 0 1 0 1
3
TOI2019 初選 pE subtask1
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~20 | 無額外限制 | 100 |