rt,bfs,在使用struct + std::queue时获得高达9MLE的好成绩
求问如何修改(或者直接重写?)
#include <iostream>
#include <queue>
using namespace std;
struct Point{
int x,y,step;
};
int s[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
Point tPoint(int x,int y,int step){
Point a;
a.x=x;
a.y=y;
a.step=step;
return a;
}
queue<Point> list;
bool map[1005][1005];
int x1,y1,x2,y2,n;
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char c;
cin>>c;
if(c=='0'){
map[i][j]=1;
}
}
}
cin>>x1>>y1>>x2>>y2;
list.push(tPoint(x1-1,y1-1,0));
while(!list.empty()){
Point t=list.front();
list.pop();
map[t.x][t.y]=0;
//cout<<t.x<<" "<<t.y<<" "<<t.step<<endl;
if((t.x==x2-1)&&(t.y==y2-1)){
cout<<t.step<<endl;
return 0;
}
for(int i=0;i<4;i++){
int px=t.x+s[i][0],py=t.y+s[i][1];
if((px<n||px>=0||py<n||py>=0)&&map[px][py]){
list.push(tPoint(px,py,t.step+1));
}
}
//cout<<list.size()<<endl;
}
return 0;
}