为啥边界问题给卡了不就是300边界

P2895 [USACO08FEB] Meteor Shower S

RainandBOW @ 2023-01-23 16:00:23

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<string,int> PSI;
#define f first
#define s second
#define pb push_back
const int N = 310;
int g[N][N];//地图
bool st[N][N];
int d[N][N];
int n;
int dx[] = {0,-1, 0, 1, 0}, dy[] = {0,0, 1, 0, -1};
queue<PII>q;
void bfs()
{
    q.push({0,0});
    st[0][0]=1;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        int t1=d[t.f][t.s]+1;
        if(g[t.f][t.s]==-1)
        {
            cout<<d[t.f][t.s]<<endl;
            return ;
        }
        for(int i=1;i<=4;i++)
        {
            int x1=t.f+dx[i],y1=t.s+dy[i];
            if(x1>=0 && x1<=301 && y1>=0 && y1<=301 && !st[x1][y1] && (g[x1][y1]==-1 || t1<g[x1][y1]))
            {
                st[x1][y1]=1;
                q.push({x1,y1});
                d[x1][y1]=t1;
            }
        }
    }
    cout<<-1<<endl;
    return ;
}
signed main()
{ 
    ios::sync_with_stdio(false);    
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    for(int i=0;i<=N;i++)
        for(int j=0;j<=N;j++)
            g[i][j]=-1;
    for(int i=1;i<=n;i++)
    {
        int x,y,t;
        cin>>x>>y>>t;
        for(int j=0;j<5;j++)
        {
            int x1=x+dx[j],y1=y+dy[j];
            if(x1>=0 && x1<=300 && y1>=0 && y1<=300 &&(g[x1][y1]==-1 || g[x1][y1]>t))
            {
                g[x1][y1]=t;
            }
        }
    }
    bfs();
    return 0;
}

by RainandBOW @ 2023-01-23 16:01:27

改成300过不了,必须要开大

if(x1>=0 && x1<=300 && y1>=0 && y1<=300 && !st[x1][y1] && (g[x1][y1]==-1 || t1<g[x1][y1]))
{
    st[x1][y1]=1;
    q.push({x1,y1});
    d[x1][y1]=t1;
}

by OldDriverTree @ 2023-01-23 16:35:10

@RainandBOW

数组越界了,应该全 \color{purple}{RE}

初始化时建议使用 memset ,用 for 循环边界条件改成 i<Nj<N

数组至少应该开 301


by RainandBOW @ 2023-01-23 16:48:34

@guoxiangyu66 我数组开了310,还能re?


by OldDriverTree @ 2023-01-23 16:49:40

@RainandBOW 初始化改成 i<Nj<N 就完全正确了


by RainandBOW @ 2023-01-23 16:50:56

@guoxiangyu66 我想问的是我dfs判断边界条件为啥300不行,必须要开大,题目不就是300


by RainandBOW @ 2023-01-23 16:52:36

@guoxiangyu66 wa最后一个点


by OldDriverTree @ 2023-01-23 16:53:34

@RainandBOW 哦,看错了


by RainandBOW @ 2023-01-23 16:53:35

@guoxiangyu66 <和<=明显就是<=更好


by OldDriverTree @ 2023-01-23 16:55:18

@RainandBOW

但是使用 <= 正常情况下都会 RE

因为数组的下标是从 0~N-1 的


by RainandBOW @ 2023-01-23 16:56:00

@guoxiangyu66 我N开到310明显比题目给的300要大10还能re?


| 下一页