Codeforces Round #243 (Div. 2)——Sereja and Table

看這個問題之前，可以先看看這個論文，說白了就是分類讨論，但是這個思想很重要

題意：

首先給出聯通塊的定義：對于相鄰（上下和左右）的相同的數字視為一個聯通塊

現給一個n*m的隻有0和1的矩形和數字k，求出最小反轉個數使得整體包括若幹個矩形聯通塊（即每個聯通塊均是矩形）(1?≤?n,?m?≤?100; 1?≤?k?≤?10)

如果最小次數比k大，輸出-1

分析：

題目的特點是k比較小，也就是說反轉的次數比較少，是以可以從這裡入手。直接枚舉所有的位置肯定是不行了，那麼可以這樣考慮：（不妨設n>=m）如果n比k大，那麼肯定有一些行是不會有反轉的數字的，那麼我們可以枚舉每一行來處理；如果k比n大，這個時候n小于10，是以這時候我們就可以暴力枚舉每一行的所有狀态，然後處理。

以上兩種方法處理的時候均依據下邊的圖形特點，隻知道一行的時候就可以求出最小的總反轉數

最終隻能是

01010...

10101...

...

的形狀（其中一個字元代表一個矩形）

參照大神的代碼後的一些細節修改：