28分BFS求助!

P2895 [USACO08FEB] Meteor Shower S

YupenBob @ 2023-09-04 22:10:18

#include <bits/stdc++.h>
using namespace std;

const int N=350;
int n;
bool m[N][N];
int tmap[N][N];
int dx[5]={0, 0, 0, 1, -1};
int dy[5]={0, 1, -1, 0, 0};
int bdx[4]={0, 0, 1, -1};
int bdy[4]={1, -1, 0, 0};
bool vis[N][N];

struct node {
    int x,y,t;
};

queue <node> que;

int main () {
    memset(m,0,sizeof(m));
    memset(tmap,0,sizeof(tmap));
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        for (int j=0;j<5;j++) {
            int nx=x+dx[j];
            int ny=y+dy[j];
            if (0<=nx&&0<=ny) {
                if (!m[nx][ny]) {
                    m[nx][ny]=1;
                    tmap[nx][ny]=t;
                }
            }
        }
    }

    que.push((node) {0,0,0});

    while (que.size()) {
        node p=que.front();
        que.pop();

        for (int i=0;i<4;i++) {
            int nx=bdx[i]+p.x;
            int ny=bdy[i]+p.y;
            int nt=1+p.t;

            if (0<=nx&&0<=ny&&(!vis[nx][ny])) {
                if (!m[nx][ny]) {
                    printf("%d",nt);
                    return 0;
                }
                else if (tmap[nx][ny]>nt) {
                    vis[nx][ny]=1;
                    que.push((node) {nx,ny,nt});
                }
            }
        }

    }

    printf("-1");
    return 0;

} 

|