心路历程

根据题面的描述，我们面临的问题无非是，每次将色块更新成什么颜色。又因为是从左上角开始更新，所以我的有了第一个想法。

将左上角的色块命名为“原色块”。

对于每个色块，定义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;
}

参考

标签：