洛谷 1162_填涂颜色_bfs

发布于 2019-05-04  5 次阅读


题目大意

将一个图中被“1”圈住的“0”填充为“2”,然后输出


思路

从每一条最外的边开始搜索,将全部在外围的0去掉,剩下的0就是2了
O(4*n^2)


#include 
#include 
using namespace std;
int a[31][31];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int n;
int bfs(int x,int y)
{
    int head=0,tail=1;
    queue tx;
    queue ty;
    tx.push(x);
    ty.push(y);
    a[x][y]=3;
    while (!tx.empty())
    {
        int xx=tx.front(),yy=ty.front();
        tx.pop(); ty.pop();
        for (int i=1;i<=4;i++)
            if (xx+dx[i]>=1&&xx+dx[i]<=n&&yy+dy[i]>=1&&yy+dy[i]<=n&&a[xx+dx[i]][yy+dy[i]]==0)
            {
                a[xx+dx[i]][yy+dy[i]]=3;
                tx.push(xx+dx[i]);
                ty.push(yy+dy[i]);
            }
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for (int i=1;i<=n;i++)
        if (a[1][i]==0) bfs(1,i);
    for (int i=1;i<=n;i++)
        if (a[i][1]==0) bfs(i,1);
    for (int i=1;i<=n;i++)
        if (a[n][i]==0) bfs(n,i);
    for (int i=1;i<=n;i++)
        if (a[i][n]==0) bfs(i,n);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            if (a[i][j]==3) printf("0 ");
                else if (a[i][j]==1) printf("%d ",a[i][j]);
                    else printf("2 ");
        printf("\n");
    }
}
]]>