比赛 |
EYOI与SBOI开学欢乐赛1st |
评测结果 |
AAWAWWAAWW |
题目名称 |
拖拉机 |
最终得分 |
50 |
用户昵称 |
Lesater |
运行时间 |
0.383 s |
代码语言 |
C++ |
内存使用 |
11.92 MiB |
提交时间 |
2022-08-29 21:10:08 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int N,xb,yb,xm,ym,ans=INT_MAX,gone[1001][1001];
int m[1001][1001];
int way[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
bool legal(int x,int y)
{
if(gone[x][y]==-1||x>=xm||y>=ym) return false;
return true;
}
void dfs(int x,int y,int cnt)
{
if(cnt>ans) return;
if(x==0||y==0)
{
ans=cnt;
return;
}
for(int i=0;i<4;++i)
{
int xx=x+way[i][0],yy=y+way[i][1];
if(legal(xx,yy))
{
if(m[xx][yy]==1)
{
gone[xx][yy]=-1;
dfs(xx,yy,cnt+1);
}
else
{
gone[xx][yy]=-1;
dfs(xx,yy,cnt);
}
}
}
return;
}
int main()
{
freopen("tractor.in","r",stdin);
freopen("tractor.out","w",stdout);
cin>>N>>xb>>yb;
gone[xb][yb]=-1;
for(int i=1;i<=N;++i)
{
int x,y;
cin>>x>>y;
if(x>xm) xm=x;
if(y>ym) ym=y;
m[x][y]=1;
}
dfs(xb,yb,0);
cout<<ans;
return 0;
}