就决定是你辣 @ 2022-09-08 17:17:44
rt,是不是状态剪枝出了问题TAT
#include<bits/stdc++.h>
using namespace std;
bool p[305][305];
bool d[305][305];
bool e[305][305];
struct node{
int t,x,y;
bool operator<(const node &a)const{return t<a.t;}
}star[50005];
queue<node>q;
int main(){
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&star[i].x,&star[i].y,&star[i].t);
}
sort(star+1,star+1+m);
for(int j=1;j<=m;j++){
d[star[j].x][star[j].y]=1;
d[star[j].x+1][star[j].y]=1;
d[star[j].x-1][star[j].y]=1;
d[star[j].x][star[j].y+1]=1;
d[star[j].x][star[j].y-1]=1;
}
q.push(node{0,0,0});
int j=1;
while(!q.empty()){
int x=q.front().x;
int y=q.front().y;
int t=q.front().t;
e[x][y]=1;
q.pop();
while(t>=star[j].t&&j<=m){
p[star[j].x][star[j].y]=1;
p[star[j].x+1][star[j].y]=1;
if(star[j].x-1>=0)p[star[j].x-1][star[j].y]=1;
p[star[j].x][star[j].y+1]=1;
if(star[j].y-1>=0)p[star[j].x][star[j].y-1]=1;
j++;
}
if(y<0||x<0||p[x][y]){
continue;
}
if(!d[x][y]){
//cout<<x<<" "<<y<<endl;
cout<<t<<endl;
return 0;
}
if(!e[x][y+1])q.push(node{t+1,x,y+1});
if(y>0||!p[x][y-1]||!e[x][y-1])q.push(node{t+1,x,y-1});
if(!e[x+1][y])q.push(node{t+1,x+1,y});
if(x>0||!p[x-1][y]||!e[x-1][y])q.push(node{t+1,x-1,y});
}
cout<<-1<<endl;
}
by 燕返 @ 2022-09-17 14:49:49
我觉得你的程序写的有问题的地方
有问题
by 就决定是你辣 @ 2023-02-26 19:39:34
我是傻逼!!!!