社区讨论
蜜汁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 条回复,欢迎继续交流。
正在加载回复...