【題解】Luogu P1162 【填涂颜色】

大爆搜

对于这种数据大小的题来说

首先预处理:

①将所有的0替换为2

②将处于边界处的2替换为0

然后进行

大爆搜

①先搜索所有的2,看其周围(4个方向)是否存在0,如果存在,就将其设为0(因为不在圈内)

②由①,我们已经扫除次外层所有的非1值了,此时可以在进行n边上述操作,直到圈外都是0,圈内都是2,圈上是1。

③但是该怎样实现呢?

很简单:

复制粘贴即可

(当然正解应该是递归)

因为这种数据规模下,绝对可以AC

C++
#include <cstdio>
using namespace std;

const int L = 48;
int map[L][L] = {};
int n;
int X[4] = {1,-1,0,0};
int Y[4] = {0,0,1,-1};

void search(int sx,int sy){
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 0){
                map[i][j] = 2;
            }
        }
    }
}

void bfs(int sx,int sy){
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2){
                if(i == 0 || j == 0){
                    map[i][j] = 0;
                   }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j] == 2 && (i > 0 && j > 0)){
                if(!map[i - 1][j] || !map[i + 1][j] || !map[i][j + 1] || !map[i][j - 1]){
                    map[i][j] = 0;
                }
            }
        }
    }

}

int main(){
    scanf("%d",&n);

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            scanf("%d",&map[i][j]);
        }
    }

    search(1,1);
    bfs(1,1);

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }

    return 0;
}