学步园

bfs裸题，注意在搜索时为了可以搜索到边缘点，应该在图像的最外一圈加上一圈1

ac代码：

 
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int map[961][1441],dir[4][2]={1,0,-1,0,0,1,0,-1},height,weight;
struct node
{
    int x, y;
};
int overmap(int x,int y)
{
    if(x<0||x>height+1||y<0||y>weight+1) return 1;
    else return 0;
}
void bfs(int a,int b)
{
    queue<node>q;
    node first,next;
    first.x=a;
    first.y=b;
    q.push(first);
    while(!q.empty())
    {
        first=q.front();q.pop();
        for(int i=0;i<4;i++)
        {
            next.x=first.x+dir[i][0];
            next.y=first.y+dir[i][1];
            if(overmap(next.x,next.y)||map[next.x][next.y]==0)
            continue;
            map[next.x][next.y]=0;
            q.push(next);
        }
    }
}
int main()
{
    int cases,i,j;
    scanf("%d",&cases);
    while(cases--)
    {
        scanf("%d%d",&weight,&height);
        for(i=1;i<=height;i++)
        {
            for(j=1;j<=weight;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        for(i=0;i<=weight+1;i++)
        {
            map[0][i]=1;
            map[height+1][i]=1;
        }
        for(i=0;i<=height+1;i++)
        {
            map[i][0]=1;
            map[i][weight+1]=1;
        }
        bfs(0,0);
        for(i=1;i<=height;i++)
        {
            for(j=1;j<weight;j++)
            {
                printf("%d ",map[i][j]);
            }
            printf("%d\n",map[i][weight]);
        }
    }
    return 0;
}