BFS求调 输出的和输入一模一样

P1162 填涂颜色

sjy_2023 @ 2023-12-09 21:51:20

题目

思路：

  1. 先认为所有的'0'都应该被修改,并且把它修改成了'2';

  2. 边角上的'2'其实本来不应该被修改的,那我们把他们改回去 ,改成'0'

  3. 然后来寻找与这些零相邻的'2',它们其实也是被改错了的 把它们改回去

#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

int n;
int a[35][35];

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

queue <int> qx;
queue <int> qy;
int flag[35][35];

int x,y;

int main()
{
    memset(flag,0,sizeof(flag));

    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {   for(int k=0;k<n;k++)
        {   scanf("%d",&a[i][k]);
            if( a[i][k]==0 && i!=0 && k!=0 )
            {   a[i][k]==2; }
        }
    }

    printf("\n");

    qx.push(1);
    qy.push(1);
    flag[1][1]=1;

    while(!qx.empty())
    {   x=qx.front();qx.pop();
        y=qy.front();qy.pop();

        for(int i=0;i<4;i++)
        {   if( x+dx[i]>=0 && x+dx[i]<n && y+dy[i]>=0 && y+dy[i]<n && flag[x+dx[i]][y+dy[i]]!=1 )
            {   qx.push(x+dx[i]);
                qy.push(y+dy[i]);
                flag[x+dx[i]][y+dy[i]]=1;
            }
        }

        if( a[x][y]==2 )
        {   if( a[x-1][y]==0 || a[x+1][y]==0 || a[x][y-1]==0 || a[x][y+1]==0 )
            {   a[x][y]=0;  }
        }
    }

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

    return 0;
}

太晚了先睡觉去了 明天回复 玄关

by sjy_2023 @ 2023-12-10 08:26:20

if( a[i][k]==0 && i!=0 && k!=0 )
            {   a[i][k]==2; }

问题在这里

by sjy_2023 @ 2023-12-10 08:28:31

AC 代码：

#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

int n;
int a[35][35];

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

queue <int> qx;
queue <int> qy;
int flag[35][35];

int x,y;

int s=0;

int main()
{
    memset(flag,0,sizeof(flag));

    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {   for(int k=0;k<n;k++)
        {   scanf("%d",&a[i][k]);
            a[i][k]=2-a[i][k];
            if( i==0 || k==0 || i==n-1 || k==n-1 )
            {   s+=1;
                qx.push(i);
                qy.push(k);
                flag[i][k]=1;
            }

        }
    }

    //printf("\n");

    qx.push(0);
    qy.push(0);
    flag[0][0]=1;

    while( !qx.empty() && !qy.empty() )
    {   x=qx.front();qx.pop();
        y=qy.front();qy.pop();

        for(int i=0;i<4;i++)
        {   if( x+dx[i]>=0 && x+dx[i]<n && y+dy[i]>=0 && y+dy[i]<n && flag[x+dx[i]][y+dy[i]]<=s )
            {   qx.push(x+dx[i]);
                qy.push(y+dy[i]);
                flag[x+dx[i]][y+dy[i]]+=1;
            }
        }

        if( a[x][y]==2 )
        {   if( a[x-1][y]==0 || a[x+1][y]==0 || a[x][y-1]==0 || a[x][y+1]==0 )
            {   a[x][y]=0;  }
        }
    }

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

    return 0;
}

by dienter @ 2023-12-10 09:08:01

@sjy_2023 关键是这样会导致全WA

by sjy_2023 @ 2023-12-10 09:13:19

@dienter 对的

上一页 |