社区讨论

蜜汁WA

P1519[USACO2.4] 穿越栅栏 Overfencing参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6gwz1h
此快照首次捕获于
2025/11/20 04:41
4 个月前
此快照最后确认于
2025/11/20 04:41
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
using namespace std;
#define RG register
#define IL inline
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>
T qget(void)
{
    T xi=0;
    char ch=getchar();
    bool f=false;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=1;
        ch=getchar( );
    }
    while( ch>='0'&&ch<='9')xi=xi*10+ch-48,ch=getchar();
    if(f)xi=-xi;
    return xi;
}
struct point
{
    int x,y,B;
    point()
    {
        B=0;
    }
    void set(int x,int y)
    {
        x=x,y=y;
    }
    point(int x,int y,int B)
    {
        x=x,y=y,B=B;
    }
};
char map[501][501];
int se[501][501];
bool visit[501][501];
int fx[4]= {0,0,1,-1}
    ,fy[4]= {1,-1,0,0},w,h;
void update(point io)
{
    se[io.x][io.y]=min(se[io.x][io.y],io.B+1);
}
bool cango(point io)
{
    if(io.x>0&&io.x<=w&&io.y>0&&io.y<=h&&!visit[io.x][io.y]&&map[io.x][io.y]==' ')return true;
    return false;
}
void bfs(queue<point>&k)
{
    while(!k.empty())
    {
        point _new=k.front();
        k.pop();
        for(int i=0; i<4; i++)
        {
            point k1(_new.x+fx[i],_new.y+fy[i],_new.B+1);
            if(cango(k1))
            {
                se[k1.x][k1.y]=min(se[k1.x][k1.y],k1.B);
                visit[k1.x][k1.y]=1;
                k.push(k1);
            }
        }
    }
}
int main()
{
    w=qget<int>(),h=qget<int>();
    w=w*2+1,h=h*2+1;
    vector<point>start;
    for(int i=1; i<=w; i++)
        for(int j=1; j<=h; j++)
        {
            scanf("%c",&map[i][j]);
            if((i==1||j==||i==w||j==h)&&map[i][j]==' ')start.push_back((point){i,j,0});
        }
    queue<point>k;
    for(int i=1; i<=500; i++)for(int j=1; j<=500; j++)se[i][j]=1000000;
    for(int i=0; i<(signed)start.size(); i++)
    {
        memset(visit,0,sizeof(visit));
        k.push(start[i]);
        bfs(k);
    }
    int maxn=-1;
    for(int i=1; i<=w; i++)for(int j=1; j<=h; j++)
            if(se[i][j]!=1000000)maxn=max(maxn,se[i][j]);
    cout<<(maxn+1)/2;
    return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...