Meteor Shower 广搜

缺乏、安全感 2022-08-08 05:21 177阅读 0赞

#include <cstdio>
    #include <queue>
    #include <cstring>
    using namespace std;
    
    #define MAX 310
    #define Inf 0x7fffffff
    
    typedef struct pot
    {
        int x, y;
        int t;
    }pot;
    int dre[5][2]={ {0,0},{0,1},{0,-1},{1,0},{-1,0} };
    int time[MAX][MAX];
    bool pos[MAX][MAX];
    
    int Min(int a, int b)
    {
        if(a<b) return a;
        return b;
    }
    bool judge_it(int x, int y)
    {
        if(x<0 || y<0) return false;
        return true;
    }
    bool judge(pot next)
    {
        if(next.x<0 || next.y<0 || next.t>=time[next.x][next.y] || pos[next.x][next.y] ) return false;
        return true;
    }
    
    int bfs()
    {
        queue<pot>Q;
        pot now, next;
    
        memset(pos, false, sizeof(pos));
        now.x=0; now.y=0; now.t=0;
        pos[now.x][now.y]=true;
        Q.push(now);
        while( !Q.empty() ){
            now=Q.front(); Q.pop();
            if(time[now.x][now.y]==Inf) return now.t;
    
            for(int i=1; i<5; i++){
                next.x=now.x+dre[i][0]; next.y=now.y+dre[i][1]; next.t=now.t+1;
                if( judge(next) ) {
                    Q.push( next );
                    pos[next.x][next.y]=true;
                }
            }
        }
        return -1;
    }
    int main()
    {
        int n;
        while( scanf("%d", &n)!=-1 ) {
            for(int i=0; i<MAX; i++){
                for(int j=0; j<MAX; j++)
                    time[i][j]=Inf;
            }
            int x, y, t;
            for(int i=0; i<n; i++){
                scanf("%d%d%d", &x, &y, &t);
                for(int j=0; j<5; j++){
                    if( judge_it(x+dre[j][0], y+dre[j][1]) ){
                        time[x+dre[j][0]][y+dre[j][1]]=Min(time[x+dre[j][0]][y+dre[j][1]], t);
                    }
                }
            }
           int ans;
           ans = bfs();
           printf("%d\n", ans);
        }
    
        return 0;
    }