flood_it 方法記錄 _生活百科

心路歷程根據題面的描述，我們面臨的問題無非是，每次將色塊更新成什么顏色。又因為是從左上角開始更新，所以我的有了第一個想法。
將左上角的色塊命名為“原色塊” 。
對于每個色塊，定義4中狀態：0-不屬于原色塊勢力，和原色塊勢力不鄰接，未沒有進行任何操作；1-不屬于原色塊勢力，和原色塊勢力鄰接，尚不知道會不會被同化（因為還不知道下一步染什么色）；2-屬于原色塊勢力，和非原色塊勢力鄰接，是上一批被同化的色塊；3-屬于原色塊勢力，和非原色塊勢力不鄰接**；
我們可以形象地依次把這四種狀態稱作“未加入”，“待審核”，“新成員”，“老成員” 。以下圖為例（顏色是色塊，數字是狀態）：

文章插圖
第一步比較特殊，因為需要求出最初的新隊員。（之后就只需要處理新成員和待審核就可以了，因為新成員處于鄰接位置，需要承擔審核工作。而老成員和未加入不需要做任何工作）
首先原色塊自身是新成員，然后跑一遍bfs，求出所有與原色塊連通且與原色塊同色的色塊，將它們都標記為新成員。
之后的每一步，首先統計與新成員鄰接且未加入的色塊，將它們標記為待審核，并統計每種顏色出現的次數。
出現次數最多的顏色就是我們即將更新的顏色。得到這個之后新成員的工作就做完了，新成員就可以標記為老成員了。
再次遍歷所有待審核的色塊，若顏色和即將更新的顏色相同，則標記為新成員；否則重新標記為未加入。
將所有新成員、老成員的顏色更新。
每次都需要判斷是否更新完整個圖。
這個算法邏輯上是行得通的，但是太慢了，因為要反復地遍歷各種狀態，導致大量無用的重復運算。
正解標算：IDA*先不談IDA* 。我們回到這道題，從模塊化編程的角度出發，想想這個程序要實現什么功能。
首先我們有更新色塊的操作。對于更新色塊的函數，我們需要3個形參：當前色塊的橫坐標、縱坐標、我們即將更新的顏色。我們仍然需要一個打標記的數組：若當前位置的顏色和即將更新的顏色相同則標記為1，反之則標記為2.所以這個函數的主要功能是給需要更新顏色的色塊打標記，還沒有進行上色操作。

void update_flags(int i,int j,int color)//color是即將更新的顏色{if(board[i][j]!=color){flags[i][j]=2;//和即將更新的顏色不同，打上標記2return ;}flags[i][j]=1;//和即將更新的顏色相同，打上標記1for(int k=0;k<4;k++){//dir[][]用于枚舉4個方向int x=i+dir[k][0];int y=j+dir[k][1];if(x<0||y<0||x>=siz||y>=siz||flags[x][y]) continue;update_flags(x,y,color);//遞歸更新尚未打標記的色塊}}

然后考慮具體的上色操作。最外層循環遍歷6種顏色，然后遍歷全圖。若當前遍歷到的位置是不同顏色且正好等于要搜索的顏色，則記錄存在這種顏色，并進行\(update_flags\).若全圖遍歷完后發現不存在這種顏色，則繼續遍歷下一個顏色。如果更新了棋盤，就遞歸搜索，成功了就返回。注意：\(flags\)數組在這個過程中可能會被改變，為了后續的使用，我們需要在操作前拷貝\(flags\)到\(tmp\)數組，操作結束后再拷貝回去。
接下來再考慮使用IDA