题解 P1162 【填涂颜色】

ps：本题题解已经70多篇了…但是翻了翻竟然没有随机化的写法，于是斗胆提交一篇hhh

重要：这个写法有小概率会错，但是胜在又快又简单，没有思维难度，而且很有意思XD，如果是考场上还可以用来骗分

基本思路如下:

• 随机生成一个点，判断这个点是否在环内，如果在，就从这个点开始floodfill（无脑泼水填充），如果不在，就重找一个点

  那么如何判断一个点在环内呢？这里的思路很简单:

• 如果向四个方向走都能碰到1,就在环内，反之不在

  这个做法当然不是保证正确的做法，而且有可能被卡（比如说有个只有一个小口的假环）但是看下数据范围，n \leq30，也就是说如果不是很刻意的卡，我们仍可以期望随机点生成在环内，正确率应该不错，事实证明，直接A了…

  记录

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1000;
const int dx[]={0,0,-1,0,1},
          dy[]={0,1,0,-1,0};
//方向数组，不写大小代表视初始值情况而定
int a[MAXN][MAXN];
int n;

bool chk(int x,int y){
    if(a[x][y]==1)return false;
    //这里要注意，如果本来就是1就别找了，直接返回
    bool v1=false,v2=false,v3=false,v4=false;
    for(int i=1;i<=n && x+i<=n;i++)
        if(a[x+i][y]==1 )
            v1=true;
    for(int i=1;i<=n && y+i<=n;i++)
        if(a[x][y+i]==1 )
            v2=true;
    for(int i=1;i<=n && x-i>=0;i++)
        if(a[x-i][y]==1 )
            v3=true;
    for(int i=1;i<=n && y-i>=0;i++)
        if(a[x][y-i]==1 )
            v4=true;
    return v1 && v2 && v3 && v4;
}

bool vis[MAXN][MAXN]={0};
void fld_fill(int x,int y){
    if(a[x][y]==1 || vis[x][y])return ;
    //如果碰到边界或者泼过的点就返回
    vis[x][y]=true;
    a[x][y]=2;
    for(int i=1;i<=4;++i)
        fld_fill(x+dx[i],y+dy[i]);
}

int main(){
    srand(rand());//随机种子
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            scanf("%d",&a[i][j]);

    while(true){
        int x=rand()%n+1,y=rand()%n+1;
        //我们的点的坐标应该是1-n之间的
        bool flag=chk(x,y);
        if(flag){//如果在环内就泼水，否则再找一个点
            fld_fill(x,y);
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j)
                    printf("%d ",a[i][j]);
                printf("\n");
            }
            return 0;
        }
    }
}