玄关求调！第二个点RE！大神赐教

zhuxuanze @ 2024-08-18 10:16:18

#include<bits/stdc++.h> 
using namespace std;
int m,visi[550][550],safe[550][550],ways[10][2]={{1,0},{-1,0},{0,1},{0,-1}},x,y,t,ans=0x7f;
struct node{
    int xx,yy,steps;
};
queue<node>q;
int bfs()
{
    node now,nex;
    now.xx=1,now.yy=1,now.steps=0; 
    visi[1][1]=0;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(safe[now.xx][now.yy]==0x7f7f7f7f)
            return ans=now.steps;
        for(int i=0;i<4;i++)
        {
            if(now.xx+ways[i][0]>=0&&now.yy+ways[i][1]>=0)
            {
                nex.xx=now.xx+ways[i][0],nex.yy=now.yy+ways[i][1],nex.steps=now.steps+1;
                if(safe[nex.xx][nex.yy]>nex.steps&&visi[nex.xx][nex.yy])
                {
                    q.push(nex);
                    visi[nex.xx][nex.yy]=0;
                }
            }
        }
    }
}
signed main()
{
    scanf("%d",&m);
    for(int i=0;i<=500;i++)
        for(int j=0;j<=500;j++)
            visi[i+1][j+1]=1;
    memset(safe,0x7f,sizeof(safe));
    for(int j=1;j<=m;j++)
    {
        scanf("%d%d%d",&x,&y,&t);
        safe[x+1][y+1]=min(safe[x+1][y+1],t);
        for(int i=0;i<4;i++)
            if(x+ways[i][0]+1>0&&y+ways[i][1]+1>0)
            {
                safe[x+ways[i][0]+1][y+ways[i][1]+1]=min(safe[x+ways[i][0]+1][y+ways[i][1]+1],t);
            } 
    }
    bfs();
    if(ans==0x7f)
        cout<<-1;
    else
        cout<<ans;
    return 0;
} 

by Lijiangjun4 @ 2024-08-18 10:48:29

你在输入的时候把坐标都改为了从1开始的，但你第22行条件判断是 >=0，你看看是不是这个问题。

by zhuxuanze @ 2024-08-18 14:01:29

@Lijiangjun4 还是错

#include<bits/stdc++.h> 
using namespace std;
int m,visi[550][550],safe[550][550],ways[10][2]={{1,0},{-1,0},{0,1},{0,-1}},x,y,t,ans=0x7f;
struct node{
    int xx,yy,steps;
};
queue<node>q;
int bfs()
{
    node now,nex;
    now.xx=1,now.yy=1,now.steps=0; 
    visi[1][1]=0;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(safe[now.xx][now.yy]==0x7f7f7f7f)
            return ans=now.steps;
        for(int i=0;i<4;i++)
        {
            if(now.xx+ways[i][0]>0&&now.yy+ways[i][1]>0)
            {
                nex.xx=now.xx+ways[i][0],nex.yy=now.yy+ways[i][1],nex.steps=now.steps+1;
                if(safe[nex.xx][nex.yy]>nex.steps&&visi[nex.xx][nex.yy])
                {
                    q.push(nex);
                    visi[nex.xx][nex.yy]=0;
                }
            }
        }
    }
}
signed main()
{
    scanf("%d",&m);
    for(int i=0;i<=500;i++)
        for(int j=0;j<=500;j++)
            visi[i+1][j+1]=1;
    memset(safe,0x7f,sizeof(safe));
    for(int j=1;j<=m;j++)
    {
        scanf("%d%d%d",&x,&y,&t);
        safe[x+1][y+1]=min(safe[x+1][y+1],t);
        for(int i=0;i<4;i++)
            if(x+ways[i][0]+1>0&&y+ways[i][1]+1>0)
            {
                safe[x+ways[i][0]+1][y+ways[i][1]+1]=min(safe[x+ways[i][0]+1][y+ways[i][1]+1],t);
            } 
    }
    bfs();
    if(ans==0x7f)
        cout<<-1;
    else
        cout<<ans;
    return 0;
} 

by Lijiangjun4 @ 2024-08-18 19:07:20

那你边界判断的时候多判下 <550 试试

by Lijiangjun4 @ 2024-08-18 19:08:50

有可能你 bfs 的时候还没找到答案就越界

by zhuxuanze @ 2024-08-23 22:25:05

@Lijiangjun4 关了O2优化就好了 此帖结！！