题解 P1162 【填涂颜色】

· · 题解

P1162 填涂颜色 题解

做完好题写题解是一个好习惯,并且我并没有在题解中找到像我一样优秀（复杂）的思路。

感受:

我做完题（AC）后看了看题解，“我在想什么啊！！！”，原来这道试炼场水题只需要1个dfs/bfs即可，而聪明（呵呵）的我竟然想到了使用3个dfs并且dfs套dfs的做法。

思路:

第一步，读图（依题面），我们读入01图。

第二步，如同P1451 求细胞数量一样，我们循环找到01图中为0的点，并进行dfs1接dfs2。

dfs1: 作用是搜索与外界相连的点（即闭合圈外的点），搜索原理，无脑暴搜。从当前点开始搜索，如果搜索到外面（图的边界以外的点），就停止搜索。搜索时我们假设当前搜索的点就是闭合圈内的点，并把它的赋值从1变成2。因为闭合圈内的点与外界不连通，所以我们在暴力搜索闭合圈内的点时并不会搜索到图边界以外的点，dfs可以正常递归推出。而若dfs搜索到了图边界以外的点，说明这一整片连通的区域都是“0”，即都是闭合圈外的点，我们需要给他们再做一个标记“-1”，表示他们已经被dfs1搜索过并且是闭合圈外的点，于是这就成为了dfs2的任务。

dfs2: 我们需要dfs2这个dfs1搜索到的在边界上的点，把与他连通的所有“2”和“0”都赋值成“-1”，因为这个点在闭合圈外，所以dfs2会被“1”所阻挡，不会影响到闭合圈内的“2”。

单纯讲解有些生涩（尤其是遇到想我这样..的算法），我们不妨使用样例解释下。

（另：事实上dfs1和dfs2在某一时间段内是同时进行的，只是开始时刻上dfs1较dfs2更早一些。）

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

看上面的01图，我们在dfs1之后圈内应该都会变成“2”。但由于dfs1和dfs2同时进行的原因，我们只能展示dfs1和dfs2都停止时的结果,如下（注意区分“1”和“-1”）:

-1 -1 -1 -1 -1 -1
-1 -1  1  1  1  1
-1  1  1  2  2  1
 1  1  2  2  2  1
 1  2  2  2  2  1
 1  1  1  1  1  1

dfs1和dfs2代码：

void dfs2(int x,int y)
{
    f[x][y]=-1;//赋值成“-1”
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&f[nx][ny]==2){
            dfs2(nx,ny);
        }
    }
    return;
}
int dfs1(int x,int y)
{
    f[x][y]=2;//赋值成“2”
    int rettt=0;
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1||nx>n||ny<1||ny>n){
            dfs2(x,y);
            rettt=-1;
            break;//快速退出
        }else if(f[nx][ny]==0){
            int ret=dfs1(nx,ny);
            if(ret==-1){
                return -1;
            }
        }
    }
    return rettt;//单一出口
}

第三步，输出，其实已经结束了，我们发现这个图已经达成了题中所求，只需要：

printf("%d ",f[i][j]==-1?0:f[i][j]);

咦？你不是说有3个dfs吗？？

是的，dfs3是用来防止被卡特殊数据（dfs1退出不及时造成的多余的“2”）而构造的暴力函数，其作用就是再次处理一遍圈外的点，循环找“-1”的位置，dfs3这个“-1”的位置，把所有搜索到得“-1”和“2”全部制成“0”，保证输出的正确性。

dfs3结果如下：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

dfs3代码：

void dfs3(int x,int y)
{
    f[x][y]=0;
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&(f[nx][ny]==-1||f[nx][ny]==2)){
            dfs3(nx,ny);
        }
    }
    return;
}

接着只需要：

printf("%d ",f[i][j]);

即可完成题目。

完整代码：

#include<cstdio>
int f[31][31];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,-1,0,1,0};
int n;
//状态：1表示墙，0表示未进行过任何搜索的点，2表示已搜索并做暂时标记点，-1表示闭合圈以外的点 
void dfs3(int x,int y)
{
    f[x][y]=0;
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&(f[nx][ny]==-1||f[nx][ny]==2)){
            dfs3(nx,ny);
        }
    }
    return;
}
void dfs2(int x,int y)
{
    f[x][y]=-1;
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&f[nx][ny]==2){
            dfs2(nx,ny);
        }
    }
    return;
}
int dfs1(int x,int y)
{
    f[x][y]=2;
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1||nx>n||ny<1||ny>n){
            dfs2(x,y);
            return -1;
        }else if(f[nx][ny]==0){
            int ret=dfs1(nx,ny);
            if(ret==-1){
                return -1;
            }
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&f[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j]==0){
                dfs1(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j]==-1){
                dfs3(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",f[i][j]);
        }
        printf("\n");
    }
    return 0;
}

优化方案：

虽然我知道这个算法太水基本上是暴力，但是暴力也是可以优化的。

dfs3的用途过小，只是为了避免特殊情况，但却又搜了一遍图，我们可以使用2个dfs，让dfs1在搜索到边界后只把该边界上的点制成“-1”，而并不启用dfs2,。等待dfs1全部走完后再直接启用dfs3，即可双dfs解决问题。

代码：

#include<cstdio>
int f[31][31];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,-1,0,1,0};
int n;
void dfs3(int x,int y)
{
    f[x][y]=0;
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&(f[nx][ny]==-1||f[nx][ny]==2)){
            dfs3(nx,ny);
        }
    }
    return;
}
void dfs1(int x,int y)
{
    f[x][y]=2;
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1||nx>n||ny<1||ny>n){
            f[x][y]=-1;
        }else if(f[nx][ny]==0){
            dfs1(nx,ny);
        }
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&f[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j]==0){
                dfs1(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j]==-1){
                dfs3(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",f[i][j]);
        }
        printf("\n");
    }
    return 0;
}

给大家看个震惊的东西：

注意所有时空数据都是luogu在没有开O2,没有快读快写，没有常数优化，的情况下实测得出。

非优化3个dfs用了15ms，且占用空间较大，而优化后2个dfs仅用时10ms,空间占用较小。

而其他题解的解法多为12-14ms，都没有达到我的10ms的水平！！

所以说，这其实是该题在时间复杂度上的最优解法。

（另：对数据有疑问的同学情搜索我的该题提交记录。）

By Mubuky