有两个点MLE了,求路过的好心人帮忙看一下

P2385 [USACO07FEB] Bronze Lilypad Pond B

Lycdeer @ 2024-06-30 14:08:06

#include<bits/stdc++.h>
using namespace std;
int g[50][50]; 
int m,n,m1,m2,qx,qy,zx,zy;
struct node{
    int x,y,z;
};
queue<node> q;
int main(){
    scanf("%d%d%d%d",&m,&n,&m1,&m2);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&g[i][j]);
            if(g[i][j]==3) qx=i,qy=j;
            if(g[i][j]==4) zx=i,zy=j;
        }
    }
    int fm1=0-m1,fm2=0-m2;
    int dx[8]={m1,m1,m2,m2,fm1,fm1,fm2,fm2};
    int dy[8]={m2,fm2,m1,fm1,m2,fm2,m1,fm1};
    q.push(node{qx,qy,0});
    while(!q.empty()){
        node k=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int kx=k.x+dx[i],ky=k.y+dy[i];
            if(1<=kx&&kx<=m&&1<=ky&&ky<=n){
                if(g[kx][ky]==1) q.push(node{kx,ky,k.z+1});
                if(g[kx][ky]==4){
                    cout<<k.z+1;
                    return 0;
                }
            }
        }
    }
    return 0;
}

by TPJ_XiaoJing @ 2024-06-30 14:52:42

@Lycdeer

队列中没有对访问过的节点做标记,导致队列里可能有大量的重复节点,建议使用标记数组改进。


by Lycdeer @ 2024-06-30 18:38:07

@TPJ_XiaoJing

已经过了 ,十分感谢你的好心。


|