flood_it 方法記錄

• 2022 年 10 月 10 日
• 筆記

心路歷程

根據題面的描述，我們面臨的問題無非是，每次將色塊更新成什麼顏色。又因為是從左上角開始更新，所以我的有了第一個想法。

將左上角的色塊命名為「原色塊」。

對於每個色塊，定義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;//和即將更新的顏色不同，打上標記2 
        return ;
    }
    flags[i][j]=1;//和即將更新的顏色相同，打上標記1 
    for(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.IDA可以理解為以迭代加深DFS的搜索框架為基礎，把原來簡單的深度限制加強為：若當前深度+未來估計步數>深度限制，則立即從當前分支回溯

具體到本題，我們的估價函數就應該是：如果顏色數量大於剩餘步數，則行不通。所以我們還需要一個計算剩餘顏色數量的函數。

int color_cnt()
{
    int ret=0;
    int s=0;
    for(int i=0;i<siz;i++)
        for(int j=0;j<siz;j++)
            if(flags[i][j]!=1)
                s|=(1<<board[i][j]);
    while(s)//檢查還有幾種顏色 
    {
        ret+=s&1;
        s>>=1;
    }
    return ret;
}

並且，我們要在主函數中枚舉每一種最大限定深度。

最終程式碼呈現如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15;
int siz;
int board[N][N];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int flags[N][N];
int max_depth;
void update_flags(int i,int j,int color)//color是即將更新的顏色 
{
    if(board[i][j]!=color)
    {
        flags[i][j]=2;//和即將更新的顏色不同，打上標記2 
        return ;
    }
    flags[i][j]=1;//和即將更新的顏色相同，打上標記1 
    for(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);//遞歸更新尚未打標記的色塊 
    }
}
int color_cnt()
{
    int ret=0;
    int s=0;
    for(int i=0;i<siz;i++)
        for(int j=0;j<siz;j++)
            if(flags[i][j]!=1)
                s|=(1<<board[i][j]);
    while(s)//檢查還有幾種顏色 
    {
        ret+=s&1;
        s>>=1;
    }
    return ret;
}
int dfs(int depth)
{
	//如果顏色數量大於剩餘步數，則行不通（估價函數） 
    if(color_cnt()>max_depth-depth)
        return 0;
    //如果當前深度剛好等於最大深度，說明已經找完了 
    if(depth==max_depth)
        return 1;
    int tmp[N][N];
    int color_exist;
    memcpy(tmp,flags,sizeof(flags));
    for(int color=0;color<6;color++)
    {
        color_exist=0;
        for(int i=0;i<siz;i++)
            for(int j=0;j<siz;j++)//當前位置是不同顏色且正好等於要搜索的顏色 
                if(flags[i][j]==2&&board[i][j]==color)
                {
                    color_exist=1;
                    update_flags(i,j,color);
                }
        //顏色不存在，繼續搜索 
        if(!color_exist) continue;
        //如果更新了棋盤，就遞歸搜索，成功則返回 
        if(dfs(depth+1)) return 1;
        memcpy(flags,tmp,sizeof(flags));
    }
    return 0;
}
int main()
{
    while(scanf("%d",&siz)&&siz)
    {
        for(int i=0;i<siz;i++)
            for(int j=0;j<siz;j++)
                scanf("%d",&board[i][j]);
        //限定最大深度 
        for(max_depth=0;;max_depth++)
        {
            memset(flags,0,sizeof(flags));
            update_flags(0,0,board[0][0]);
            if(dfs(0)) break;
        }
        printf("%d\n",max_depth);
    }
    return 0;
}

參考