比赛 |
EYOI与SBOI开学欢乐赛1st |
评测结果 |
AAAAWAWWWW |
题目名称 |
拖拉机 |
最终得分 |
50 |
用户昵称 |
op_组撒头屯 |
运行时间 |
0.605 s |
代码语言 |
C++ |
内存使用 |
19.54 MiB |
提交时间 |
2022-08-29 19:46:31 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=50000+5;
const int M=1000+5;
const int inf=0x3f3f3f3f;
int n,mxx=0,mxy=0;
int id[M][M]={0},cnt=0,val[M*M];
bool mp[M][M]={0},vis[M][M]={0};
inline void fld(int x,int y,int cnt){
if (id[x][y]!=0)return ;
id[x][y]=cnt;
if (x!=0&&mp[x-1][y]!=1)fld(x-1,y,cnt);
if (y!=0&&mp[x][y-1]!=1)fld(x,y-1,cnt);
if (x!=mxx+1&&mp[x+1][y]!=1)fld(x+1,y,cnt);
if (y!=mxy+1&&mp[x][y+1]!=1)fld(x,y+1,cnt);
return ;
}
struct sdf{
int id,cnt;
}fir[M*M];
queue<sdf>q;
stack<int>st;
inline void dfs(int x,int y,int cnt){
if (vis[x][y]==1)return ;
vis[x][y]=1;
if (x!=0){
if (mp[x-1][y]==1){
if (val[id[x-2][y]]>cnt){
st.push(id[x-2][y]);val[id[x-2][y]]=cnt;
}
}
else{
if (vis[x-1][y]==0)dfs(x-1,y,cnt);
}
}
if (y!=0){
if (mp[x][y-1]==1){
if (val[id[x][y-2]]>cnt){
st.push(id[x][y-2]);val[id[x][y-2]]=cnt;
}
}
else{
if (vis[x][y-1]==0)dfs(x,y-1,cnt);
}
}
if (x!=mxx+1){
if (mp[x+1][y]==1){
if (val[id[x+2][y]]>cnt){
st.push(id[x+2][y]);val[id[x+2][y]]=cnt;
}
}
else{
if (vis[x+1][y]==0)dfs(x+1,y,cnt);
}
}
if (y!=mxy+1){
if (mp[x][y+1]==1){
if (val[id[x][y+2]]>cnt){
st.push(id[x][y+2]);val[id[x][y+2]]=cnt;
}
}
else{
if (vis[x][y+1]==0)dfs(x,y+1,cnt);
}
}
}
int main(){
freopen ("tractor.in","r",stdin);
freopen ("tractor.out","w",stdout);
int x,y;
scanf("%d%d%d",&n,&x,&y);
for (int i=1;i<=n;i++){
int a,b;scanf("%d%d",&a,&b);
mp[a][b]=1;mxx=max(mxx,a);mxy=max(mxy,b);
}
bool yes=0;
if (mp[1][1]==1){
mp[1][1]=0;yes=1;
}
fld(0,0,++cnt);fir[cnt]={0,0};
for (int i=1;i<=mxx;i++){
for (int j=1;j<=mxy;j++){
if (mp[i][j]==0&&id[i][j]==0){
fld(i,j,++cnt);fir[cnt]={i,j};
}
}
}
memset(val,0x3f,sizeof(val));
q.push({id[x][y],0});val[id[x][y]]=0;
while(!q.empty()){
sdf t=q.front();q.pop();
memset(vis,0,sizeof(vis));
dfs(fir[t.id].id,fir[t.id].cnt,t.cnt+1);
while(!st.empty()){
int tmp=st.top();
q.push({tmp,t.cnt+1});
st.pop();
}
if (val[id[1][1]]!=inf){
break;
}
}
if (yes==1)val[id[1][1]]++;
printf("%d\n",val[id[1][1]]);
return 0;
}