P3156 营救计划 TLE50分怎么优化？

[汪子越]

#include<bits/stdc++.h>
using namespace std;
struct xx{
int x,y,step;
};
int sx,sy,ans=2000000000,nx,ny,ex,ey;
int n,m,fx[4]={1,-1,0,0},fy[4]={0,0,-1,1},st[1002][1002]={0};
char dt[1001][1001];
void bfs(){
queue q;
q.push(xx{sx,sy});
while(q.size()>0){
xx now=q.front();
q.pop();
if(st[now.x][now.y]==0) st[now.x][now.y]=now.step;
else st[now.x][now.y]=min(st[now.x][now.y],now.step);
for(int i=0;i<4;i++){
nx=now.x+fx[i];
ny=now.y+fy[i];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&dt[nx][ny]!=‘#’){
if(st[nx][ny]==0||st[nx][ny]>now.step){
if(st[ex][ey]==0||now.step<st[ex][ey]){
if(dt[nx][ny]==‘G’) q.push(xx{nx,ny,now.step+2});
else q.push(xx{nx,ny,now.step+1});
}
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>dt[i][j];
if(dt[i][j]==‘@’){
sx=i;
sy=j;
}
if(dt[i][j]==‘M’){
ex=i;
ey=j;
}
}
}
bfs();
if(st[ex][ey]!=0) cout<<st[ex][ey];
else cout<<“You can’t save Mengxin”;
}

[申希远]

发一下题面

[徐梓豪]

cin改scanf

cout改printf

这样逝世

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

@汪子越

if(st[now.x][now.y]==0) st[now.x][now.y]=now.step;
else st[now.x][now.y]=min(st[now.x][now.y],now.step);

这个放在for循环力就好了

if(vis[nx][ny]&&time>=ans[nx][ny]) continue;

然而你可以在while循环里判断是否是终点，而不是for循环里平白增加复杂度

if(now.x==ex && now.y==ey)