求助,最后一个点过不去

P2895 [USACO08FEB] Meteor Shower S

象龟迭戈 @ 2021-10-25 17:02:27

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
//#define MAXN
using namespace std;
typedef long long ll;
int m,d[305][305],timee[305][305];//d记录答案   timee记录(x,y)位置陨石砸落的最小时间 
bool flag,v[305][305];//flag用来判断是否到达安全位置  v实现不走回头路 
int ed[5][5]={
{},
{0,1,0},
{0,0,-1},
{0,-1,0},
{0,0,1},
};//四个方向 
struct Node{
    int x,y,ttime;
}pla;
queue<Node> q;
//const ll mod=
int read();
void bfs();
bool check(int x,int y,int z);
int main()
{
    m=read();
    for(int i=0;i<=300;i++)
        for(int j=0;j<=300;j++) timee[i][j]=1005;//初始化 
    pla.x=0;
    pla.y=0;
    pla.ttime=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read();
        y=read();
        z=read();
        timee[x][y]=min(timee[x][y],z);
        for(int j=1;j<=4;j++)
        {
            int dx=x+ed[j][1];
            int dy=y+ed[j][2];
            if(dx>=0&&dy>=0) timee[dx][dy]=min(timee[dx][dy],z);//记录陨石砸落的最小时间 
        }
    }
//  for(int i=0;i<=5;i++)
//  {
//      for(int j=0;j<=5;j++)
//          cout<<time[i][j]<<" ";
//      cout<<endl;
//  }
    bfs();
    if(!flag) printf("-1");//如果未能到达安全位置则输出-1 
    return 0;
}
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<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return f*x;
}
void bfs()
{
    q.push(pla);
    v[0][0]=1;
    while(!q.empty())
    {
        Node e=q.front();
        q.pop();
        for(int i=1;i<=4;i++)
        {
            int dx=e.x+ed[i][1];
            int dy=e.y+ed[i][2];
            if(!check(dx,dy,e.ttime+1)) continue;//判断该位置能不能走 
            if(v[dx][dy]) continue;
            Node dd;
            dd.x=dx;
            dd.y=dy;
            dd.ttime=e.ttime+1;
            if(timee[dx][dy]==1005)//如果下个位置没有陨石则输出 
            {
                flag=1;
                printf("%d",e.ttime+1);
                return ;
            }
            if(!d[dx][dy]) d[dx][dy]=e.ttime+1,q.push(dd),v[dx][dy]=1;
        }
    }
}
bool check(int x,int y,int z)//判断能不能走 
{
    if(x>=0&&y>=0&&z<timee[x][y]) return 1;
    else return 0;
}

by __hacker__ @ 2021-10-27 02:32:35

最后一个点是超出300这个范围了,也满足要求


by 象龟迭戈 @ 2021-10-28 14:23:04

@hacker 但是我开的比300大啊,而且判断条件也没有限制300


by __hacker__ @ 2021-10-28 16:50:11

你初始化的时候就到300,应该再大一点


|