P2895 [USACO08FEB]流星雨Meteor Shower

预处理出每个位置最早被摧毁的时间，在此之前都可以走

直接dfs加个记忆化和最优性剪枝就好了

一定要注意流星的边界，如果波及到负数坐标的位置不要去考虑会RE

一定要考虑流星砸到边界的情况如 (300,300) 那么(300,301) 和 (301,300) 的位置都会被波及不安全，也要考虑到

注意奶牛可以跑出边界！比如（301,300）

代码简单，就不注释了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=307,xx[4]={0,1,0,-1},yy[4]={1,0,-1,0};
int n,ans=1e9;
int mp[N][N],f[N][N];
void dfs(int x,int y,int stp)
{
    if(stp>=ans||(mp[x][y]!=-1&&stp>=mp[x][y])) return;
    if(f[x][y]&&f[x][y]<=stp) return;
    f[x][y]=stp; if(mp[x][y]==-1) { ans=stp; return; }
    for(int k=0;k<4;k++)
    {
        if(x+xx[k]<0||y+yy[k]<0) continue;
        dfs(x+xx[k],y+yy[k],stp+1);
    }
}
int main()
{
    memset(mp,-1,sizeof(mp));
    int a,b,c;
    n=read();
    for(int i=1;i<=n;i++)
    {
        a=read(); b=read(); c=read();
        if(mp[a][b]>c||mp[a][b]==-1) mp[a][b]=c;
        for(int k=0;k<4;k++)
        {
            int x=a+xx[k],y=b+yy[k];
            if(x<0||y<0) continue;
            if(mp[x][y]>c||mp[x][y]==-1) mp[x][y]=c;
        }
    }
    dfs(0,0,0);
    printf("%d",ans==1e9 ? -1 : ans);
    return 0;
}

P2895 [USACO08FEB]流星雨Meteor Shower

相关推荐