有哪位大神帮我看一下哪里需要优化,本咸鱼已经努力优化一次了!(使用了布尔型防重复走路数组)
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,t;
};
queue<node> walk;
int farm[305][305],meteor[50000][3],m;
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
bool vis[305][305];
void bfs(){
int i,j,x,y,t,tx,ty;
node tmp,cur;
tmp.x=0;
tmp.y=0;
tmp.t=0;
walk.push(tmp);
while(!walk.empty()){
cur=walk.front();
x=cur.x;
y=cur.y;
t=cur.t;
vis[x][y]=true;
//cout<<x<<" "<<y<<" "<<t<<endl;
if(farm[x][y]==0){
cout<<t;
return;
}
for(i=0;i<m;i++){
if(t==meteor[i][2]){
tx=meteor[i][0];
ty=meteor[i][1];
farm[tx][ty]=1;
//cout<<tx<<" "<<ty<<endl;
for(j=0;j<4;j++){
//cout<<" "<<tx+dx[j]<<" "<<ty+dy[j]<<endl;
if(tx+dx[j]>=0&&ty+dy[j]>=0)
farm[tx+dx[j]][ty+dy[j]]=1;
}
}
}
/*for(i=0;i<4;i++){
for(int j=0;j<4;j++){
cout<<farm[i][j]<<"\t";
}
cout<<endl;
}*/
if(farm[x][y]==1){
/*cout<<-1;
return;*/
//cout<<"boom"<<endl;
walk.pop();
continue;
}
for(i=0;i<4;i++){
tx=x+dx[i];
ty=y+dy[i];
if(tx>=0&&ty>=0){
if(farm[tx][ty]!=1&&!vis[tx][ty]){
tmp.x=tx;
tmp.y=ty;
tmp.t=t+1;
walk.push(tmp);
}
}
}
//t++;
walk.pop();
}
cout<<-1;
}
int main(){
int i,j,x,y;
cin>>m;
for(i=0;i<m;i++){
cin>>meteor[i][0]>>meteor[i][1]>>meteor[i][2];
x=meteor[i][0];
y=meteor[i][1];
farm[x][y]=-1;
for(j=0;j<4;j++){
//cout<<x+dx[j]<<" "<<y+dy[j]<<endl;
if(x+dx[j]>=0&&y+dy[j]>=0)
farm[x+dx[j]][y+dy[j]]=-1;
}
}
bfs();
return 0;
}
另外加注释的地方是用来调试的,供大家使用(微笑)(明明是懒得删)