求助，BFS样例过不了（玄1关）

WJX120423 @ 2024-06-27 08:49:24

#include<bits/stdc++.h>
using namespace std;
int ans=INT_MAX;
int n;
int a[310][310];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct node{
    int x,y,step;
    node(int xx,int yy,int st){
        x=xx; y=yy; step=st;
    }
};
queue<node> q;
void bfs(){
    q.push(node(0,0,0));
    while(!q.empty()){
        node nd=q.front(); q.pop();
        if(a[nd.x][nd.y]>=0x7f){
            ans=min(ans,nd.step);
            continue;
        }
        for(int i=0;i<4;i++){
            int xx=nd.x+dx[i];
            int yy=nd.y+dy[i];
            if(xx>=0&&yy>=0&&a[xx][yy]>nd.step+1){
                q.push(node(xx,yy,nd.step+1));
            }
        }
    }
}
int main(){
    memset(a,0x7f,sizeof(a));
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        a[x][y]=min(w,a[x][y]);
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=x+dy[i];
            if(xx>=0&&yy>=0) a[xx][yy]=min(a[xx][yy],w);
        }
    }
    bfs();
    cout<<ans;
    return 0;
}

by jasonyjm @ 2024-06-27 09:58:38

让我们实验一下你的代码

by zhangqiuyanAFOon2024 @ 2024-07-09 23:24:35

A了

#include<bits/stdc++.h>
#define inf INT_MAX
using namespace std;
int ans=inf;
int n;
int a[310][310],vis[310][310];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct node{
    int x,y,step;
    node(int xx,int yy,int st){
        x=xx; y=yy; step=st;
    }
};
queue<node> q;
void bfs(){
    q.push(node{0,0,0});
    vis[0][0]=1;
    while(!q.empty()){
        node nd=q.front(); 
        q.pop();
        for(int i=0;i<4;i++){
            int xx=nd.x+dx[i];
            int yy=nd.y+dy[i];
            if(xx>=0&&yy>=0&&a[xx][yy]>nd.step+1&&!vis[xx][yy]){
                if(a[xx][yy]==inf){
                    ans=nd.step+1;
                    return;
                }
                q.push(node{xx,yy,nd.step+1});
                vis[xx][yy]=1;
            }
        }
    }
}
int main(){
    for(int i=0;i<=301;i++)
        for(int j=0;j<=301;j++)
            a[i][j]=inf;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        a[x][y]=min(w,a[x][y]);
        for(int j=0;j<4;j++){
            int xx=x+dx[j];
            int yy=y+dy[j];
            if(xx>=0&&yy>=0) a[xx][yy]=min(a[xx][yy],w);
        }
    }
    bfs();
    cout<<(ans==INT_MAX?-1:ans);
    return 0;
}