代码过于混乱，感觉无药可救了，我是不是废了

P1162 填涂颜色

renzecheng @ 2023-07-12 21:09:57

32，

1，5过了

#include<iostream>
using namespace std;
int a[101][101];
int ans=2,f=0,n;
void bfs(int fx,int fy)
{
    if(a[fx][fy]==1||a[fx][fy]==ans)
    {
        return;
    }
    if(fx<=1||fx>=n||fy<=1||fy>=n)
    {
        f=1;
        return;
    }
    a[fx][fy]=ans;
    bfs(fx+1,fy);
    bfs(fx,fy+1);
    bfs(fx-1,fy);
    bfs(fx,fy-1);
}
int main()
{
    int x,y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==0)
            {
                f=0;
                bfs(i,j);
                if(f==1)
                {
                    for(int k=1;k<=n;k++)
                    {
                        for(int l=1;l<=n;l++)
                        {
                            if(a[k][l]==ans)
                            {
                                a[k][l]=-1;
                            }
                        }
                    }
                    ans++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==-1||a[i][j]==0)
            {
                cout<<0;
            }
            else if(a[i][j]==1)
            {
                cout<<1;
            }
            else 
            {
                cout<<2;
            }
//          cout<<a[i][j];
            cout<<' ';
        }
        cout<<endl;
    }
    return 0;
}

by WangYinxiAlex @ 2023-07-31 14:17:23

@renzecheng What······ 没看懂你的代码，但我推荐一个想法：

#include<iostream>
using namespace std;
int a[31][31];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a[i][j];
    }
    for(int i=2;i<n;i++){
        for(int j=2;j<n;j++){
            if(a[i][j]!=1)a[i][j]=2;
        }
    }
    for(int i=2;i<n;i++){
        for(int j=2;j<n;j++){
            if(a[i][j]!=1&&\
            (a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
                a[i][j]=0;
            }
        }
    }
    for(int i=n-1;i>1;i--){
        for(int j=n-1;j>1;j--){
            if(a[i][j]!=1&&\
            (a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
                a[i][j]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

注释：

10-14行：由于最多矩形的边缘也是在最外面一周，所以最外面的0肯定都不是矩阵内的。
15-23行：从左、上方向判断这个点四周是不是有矩形外的点（0），如果有，说明这个点也不是矩形内的。
24-32行：但只从左、上方向看是不够的（如图1，这个是左、上方向的漏洞），还得从右、下方向判断。
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 1 0 0 1 1 1
1 0 1 0 0 0 0 0
1 0 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
图1
（第3行第2列、第3行第3列、第4行第2列、第4行第3列、第4行第4列均无法被赋值）

按照这个办法，可以AC。

如果AC了，别忘了关注哦~

by renzecheng @ 2023-07-31 14:56:13

@WangYinxiAlex

不用了，求助了认识的大牛

不知道为什么写成最短路了

好离谱自己再次发现了最短路算法

本来不想用的，k循环在外面就行了

这就是自己造的代码的问题

过了纯属数据太水

by WangYinxiAlex @ 2023-07-31 14:58:30

@renzecheng 哦，好吧~（看在我认真回复的份上，给个关注呗~）

by renzecheng @ 2023-07-31 15:12:51

OK

|