代码求助

doublechi @ 2022-08-11 21:32:51

#include<bits/stdc++.h>
using namespace std;
const int N=3e2+5;
int m;
int down[N][N],ans[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool check(int x,int y)
{
    if(x<0||y<0||x>N||y>N)return 1;
    return 0;
}
void add(int x,int y,int t)
{
    if(check(x,y))return;
    down[x][y]=min(down[x][y],t);
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(check(xx,yy))continue;
        down[xx][yy]=min(down[xx][yy],t);
    }
}
int bfs(int sx,int sy)
{   
    bool vis[N][N];
    memset(vis,0,sizeof(vis));
    vis[sx][sy]=1;
    queue<pair<int,int> >que;
    que.push(make_pair(sx,sy));
    ans[sx][sy]=0;
    while(que.size())
    {
        int x=que.front().first;
        int y=que.front().second;
        que.pop();
        //if(down[x][y]>=0x3f3f)
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(check(xx,yy)||vis[xx][yy])continue;
            if(ans[x][y]+1>=down[xx][yy])continue;
            vis[xx][yy]=1;
            ans[xx][yy]=ans[x][y]+1;
            que.push(make_pair(xx,yy));
        }
    }
    int ansx=1e9;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(down[i][j]>1000&&ans[i][j]!=-1)ansx=min(ansx,ans[i][j]);
            //cout<<ans[i][j]<<" ";
        }
        //cout<<endl;
    }
    if(ansx==1e9)return -1;
    return ansx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>m;
    memset(down,0x3f3f,sizeof(down));
    memset(ans,-1,sizeof(ans));
    for(int i=1;i<=m;i++)
    {
        int x,y,t;
        cin>>x>>y>>t;
        add(x,y,t);
    }
    cout<<bfs(0,0);

    return 0;
}

by 冰封侠 @ 2022-08-17 21:00:44

@zhangtinghe

第3行 const int N=3e2+5; 改成了 const int N=3e2+10;

以及第51、 53行，

for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)

改成了

for(int i=0;i<=305;i++)
for(int j=0;j<=305;j++)

首先枚举要从原点开始，而不能用N作为上限，是因为这样就枚举到数组边界了，可能会造成错误。

AC代码如下 （我知道你不会直接复制的）

#include<bits/stdc++.h>
using namespace std;
const int N=3e2+10;
int m;
int down[N][N],ans[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool check(int x,int y)
{
    if(x<0||y<0||x>N||y>N)return 1;
    return 0;
}
void add(int x,int y,int t)
{
    if(check(x,y))return;
    down[x][y]=min(down[x][y],t);
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(check(xx,yy))continue;
        down[xx][yy]=min(down[xx][yy],t);
    }
}
int bfs(int sx,int sy)
{   
    bool vis[N][N];
    memset(vis,0,sizeof(vis));
    vis[sx][sy]=1;
    queue<pair<int,int> >que;
    que.push(make_pair(sx,sy));
    ans[sx][sy]=0;
    while(que.size())
    {
        int x=que.front().first;
        int y=que.front().second;
        que.pop();
        //if(down[x][y]>=0x3f3f)
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(check(xx,yy)||vis[xx][yy])continue;
            if(ans[x][y]+1>=down[xx][yy])continue;
            vis[xx][yy]=1;
            ans[xx][yy]=ans[x][y]+1;
            que.push(make_pair(xx,yy));
        }
    }
    int ansx=1e9;
    for(int i=0;i<=305;i++)
    {
        for(int j=0;j<=305;j++)
        {
            if(down[i][j]>1000&&ans[i][j]!=-1)ansx=min(ansx,ans[i][j]);
            //cout<<ans[i][j]<<" ";
        }
        //cout<<endl;
    }
    if(ansx==1e9)return -1;
    return ansx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>m;
    memset(down,0x3f3f,sizeof(down));
    memset(ans,-1,sizeof(ans));
    for(int i=1;i<=m;i++)
    {
        int x,y,t;
        cin>>x>>y>>t;
        add(x,y,t);
    }
    cout<<bfs(0,0);

    return 0;
}

至于为什么开O2优化会RE，由于我是蒟蒻，还是找别的大佬来解决吧。

by doublechi @ 2022-08-18 09:00:01

@冰封侠

谢谢大佬，谢谢大佬