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感谢!