为什么暴力过不了?求助大佬!

P1162 填涂颜色

acmwriter @ 2022-11-30 16:18:03

#include<stdio.h>
int main()
{
    int a[50][50],n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]==1&&a[i-1][j]==0)
                a[i-1][j]=2;
            if(a[i][j]==1&&a[i+1][j]==0)
                a[i+1][j]=2;    
            if(a[i][j]==1&&a[i][j-1]==0)
                a[i][j-1]=2;
            if(a[i][j]==1&&a[i][j+1]==0)
                a[i][j+1]=2;
            if(a[i][j]==1&&a[i][j+1]==1&&a[i+1][j]==1&&a[i+1][j+1]==0)
            a[i+1][j+1]=2;
            if(a[i][j]==1&&a[i][j+1]==1&&a[i-1][j]==1&&a[i-1][j+1]==0)
            a[i-1][j+1]=2;
            if(a[i][j]==1&&a[i][j-1]==1&&a[i+1][j]==1&&a[i+1][j-1]==0)
            a[i+1][j-1]=2;
            if(a[i][j]==1&&a[i-1][j]==1&&a[i][j-1]==1&&a[i-1][j-1]==0)
            a[i-1][j-1]=2;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i-1][j]==2&&a[i+1][j]==2&&a[i][j+1]==2&&a[i][j-1]==2)
            a[i][j]=2;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]==0&&a[i-1][j]==2)
            a[i-1][j]=0;
            if(a[i][j]==0&&a[i+1][j]==2)
            a[i+1][j]=0;
            if(a[i][j]==0&&a[i][j+1]==2)
            a[i][j+1]=0;
            if(a[i][j]==0&&a[i][j-1]==2)
            a[i][j-1]=0;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(j<n-1)
            printf("%d ",a[i][j]);
            else
            printf("%d",a[i][j]);
        }
        printf("\n"); 
    }
}

by lonely_myx @ 2022-11-30 16:54:59

@acmwriter

这是一道模板搜索题,建议学bfs和dfs之后再做,想进阶可以学剪枝


by lonely_myx @ 2022-11-30 17:01:25

@acmwriter

明白了麻烦吱一声


by acmwriter @ 2022-11-30 21:34:49

@lonely_myx 感谢,明白了。


|