结构体广搜TLE

P2895 [USACO08FEB] Meteor Shower S

heyMoonquakes @ 2022-10-28 23:19:44

BFS,用结构体存储当前节点信息。 跟题解里面思路完全一致,不过他用的是两个队列分别存储x,y一个二维数组存储移动到x,y坐标所需要的时间

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int M=5e4+10;
const int N=310;

int num[N][N],m,visited[N][N];
int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 

struct Node{
    int x,y,time;
};

queue<Node> q;

int main(){
    cin>>m;
    memset(num,-1,sizeof(num));

    for(int i=0;i<m;i++){
        int t,x,y;
        scanf("%d %d %d",&x,&y,&t);
        if(t<num[x][y]||num[x][y]==-1) num[x][y]=t;
        for(int j=0;j<4;j++){
            int x1=step[j][0]+x,y1=step[j][1]+y;
            if(x1>=0&&y1>=0)    if(t<num[x1][y1]||num[x1][y1]==-1)  num[x1][y1]=t;
        }
    }
    visited[0][0]=1;
    Node now;
    now.x=0;now.y=0,now.time=0;
    q.push(now);

    int ans;
    int x1,y1,t1;
    bool flag=false;

    while(!q.empty()){
        now=q.front();
        q.pop();
        int nx=now.x,ny=now.y,nt=now.time;
        if(num[nx][ny]==-1){
            cout<<nt;
            return 0;
        }   

        for(int i=0;i<4;i++){
            x1=nx+step[i][0],y1=ny+step[i][1],t1=nt+1;
            if(x1>=0&&y1>=0&&(num[x1][y1]>t1||num[x1][y1]==-1)&&visited[x1][y1]==0){
                visited[x1][y1]==1;
                Node l;
                l.x=x1,l.y=y1,l.time=t1;
                q.push(l);
            }
        }
    }
    cout<<-1;
    return 0;

}

by saixingzhe @ 2022-11-25 19:21:44

@heyMoonquakes 你visited[x1][y1]==1;应该是visited[x1][y1]=1;亲测AC,求关


by heyMoonquakes @ 2022-11-26 12:28:13

@saixingzhe 已A感谢!


|