哈嘍各位親愛的觀眾朋友們大家好！沒錯，還是我。這次我終于做到了史無前例的一周一更。?

今天的題目和上期一樣，有那么億些些難度。但實質(zhì)上DFS用熟了還是可以解決的。代碼有些長，可能也不是最優(yōu)解法。但是總體運行時間尚可接受。讓我們點開下面的音樂，開啟今天的內(nèi)容吧！

今天我們來研究一個神奇的填色塊機器：

這個題目考點還是不少的。首先，輸入的格式是一個坐標(biāo)系的點圖。但是眾所周知我們二維數(shù)組模擬的更像是一個個方格組成的方塊圖。將點對點的輸入數(shù)據(jù)描述轉(zhuǎn)化成C++能接受的二維數(shù)組，是我們必須要克服的問題。

在簡單的實驗后，我發(fā)現(xiàn)我們可以將輸入的右下角X ，Y坐標(biāo)各減去1，配合前面的左上角數(shù)據(jù)就能夠確定該矩形左上角和右下角的方塊在數(shù)組中的方位。將“坐標(biāo)系”轉(zhuǎn)化為“方格系”，這是我處理數(shù)據(jù)的基礎(chǔ)。

相比于最關(guān)鍵而且陷阱很多的DFS函數(shù)，這樣的問題簡直就不叫問題。與DNDS吉尼斯不同，對于這段程序而言，完成了輸入后我們不需要在數(shù)據(jù)前面加上過多的處理?，F(xiàn)在，我們就要進入最關(guān)鍵的深度優(yōu)先搜索環(huán)節(jié)了。

具體的解決方案如下：

在深度優(yōu)先搜索的函數(shù)里，我將工作大致分成了一下幾步：

1. 將輸入的平板和噴涂色塊的記錄（used[30])都從輸入里復(fù)制下來。然后用復(fù)制本進行操作。這樣做是因為據(jù)我實踐發(fā)現(xiàn)，如果直接用函數(shù)里面int 的數(shù)據(jù)的話，到最后那個數(shù)組實際上就是個指針。這樣一來將數(shù)組開在函數(shù)括號里和開在括號外當(dāng)整體的數(shù)組就沒啥實質(zhì)區(qū)別了，而且回溯也相當(dāng)麻煩。

2. 設(shè)置一個終結(jié)的狀態(tài)，也就是將步數(shù)返回到ans里，將答案值更新。這里我的終結(jié)條件是我們填涂完的矩形數(shù)量等于輸入的矩形數(shù)量

3. 其他情況：繼續(xù)搜索。這里是全程序最大的難點。最外面的for循環(huán)目的是讓整個尋找+填涂環(huán)節(jié)進行4次。這個是我為了應(yīng)對特殊情況專門多寫的。就像在輸入的數(shù)據(jù)里，如果我們將示例輸入的第一個和第三個矩形描述調(diào)換一下，我的程序就有些危險了。然后就是循環(huán)選擇矩形。再往里是一個if做的基本判斷，主要檢查方塊的預(yù)定顏色是否匹配，以及該方塊是否已經(jīng)被填涂。再往里是一層循環(huán)，檢查選定的矩形是否全部被涂滿，這里會反饋一個叫“ok”的布爾型數(shù)據(jù)，這是我們決定填涂方塊的最后指標(biāo)。接著就是涂色以及計數(shù)的環(huán)節(jié)。如果本次搜索加循環(huán)有成果，那么就可以進入下一輪搜索，否則這個搜索支就此終結(jié)。

完成了一系列的循環(huán)搜索后，輸出答案，程序結(jié)束。

好啦，這一期的競賽題目就寫到這里啦。既然都看到這里了，記得一鍵三連哦！由于BNDSOJ上的數(shù)據(jù)比較弱，本期UP決定，如果點贊數(shù)量超過4個，或者閱讀量達(dá)到30，我就把這個程序放到洛谷上用加強的數(shù)據(jù)測評一下，下期公布截圖！

Ps：由于題目可能是某個競賽的原題，我就暫時不勾選原創(chuàng)了