比赛 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;
}