题解 P1849 【[USACO12MAR]拖拉机Tractor】

仰面清风 · 2018-09-08 14:51:29 · 题解

这个题目吧，看大家有用spfa的，还有用优先队列的。

但是，个人感觉，咱们模拟一下，是更简单粗暴的，实测速度142ms

思路很简单，从四个边角点向内更新，四种情况的结果取最小，就可以了叭

我是蒟蒻，各位大佬随便看看就好了

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int p[1005][1005];//图 
int n,xx,yy;
int h,r;
int f[1005][1005],g[1005][1005],w[1005][1005],z[1005][1005];
int ans;

int main()
{
    freopen("tractor.in","r",stdin);
    freopen("tractor.out","w",stdout);
    scanf("%d%d%d",&n,&xx,&yy);
    int xi,yi;
    for(register int i=1;i<=n;i++)
    {
        scanf("%d%d",&xi,&yi);
        p[xi][yi]=1;//被占据 
        h=max(h,yi); r=max(r,xi);  
    }
    //从四个点开始搜索
    for(register int i=1;i<=xx;i++)
    for(register int j=1;j<=yy;j++)
    {
        f[i][j]=min(f[i-1][j],f[i][j-1]);
        if(p[i][j])//被占据
        {
            f[i][j]++;
        } 
    }
    ans=f[xx][yy];
    //（0，0）
    for(register int i=1;i<=xx;i++)
    for(register int j=h;j>=yy;j--)
    {
        g[i][j]=min(g[i-1][j],g[i][j+1]);
        if(p[i][j])
        {
            g[i][j]++; 
        }
    }
    ans=min(ans,g[xx][yy]); 
    //左上角 
    for(register int i=r;i>=xx;i--)
    for(register int j=1;j<=yy;j++)
    {
        w[i][j]=min(w[i+1][j],w[i][j-1]);
        if(p[i][j])
        {
            w[i][j]++;
        }
    }
    ans=min(ans,w[xx][yy]);
    //右下角
    if(r<1000||h<1000) 
    {
        for(register int i=r;i>=xx;i--)
        for(register int j=h;j>=yy;j--)
        {
            z[i][j]=min(z[i+1][j],z[i][j+1]);
            if(p[i][j])
            {
                z[i][j]++;
            } 
        }
        ans=min(ans,z[xx][yy]);
    } 
    else{
        z[xx][yy]=ans;
        for(register int i=xx+1;i<=r;i++) z[i][yy]=w[i][yy];
        for(register int j=yy+1;j<=h;j++) z[xx][j]=g[xx][j];
        for(register int i=xx+1;i<=r;i++)
        for(register int j=yy+1;j<=h;j++)
        {
            z[i][j]=min(z[i-1][j],z[i][j-1]);
            if(p[i][j]) z[i][j]++;
        }
        for(register int i=r-1;i>=xx;i--)
        for(register int j=h-1;j>=yy;j--)
        {
            int temp=min(z[i+1][j],z[i][j+1]);
            if(p[i][j]) temp++;
            z[i][j]=min(z[i][j],temp);
        }
        ans=min(ans,z[xx][yy]);
    }
    cout<<ans<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0; 
}