为什么会RE！？

Shanxiao520 @ 2024-08-02 21:06:47

#include<bits/stdc++.h>
using namespace std;
int a[500][500],n,m,x,y,bj[500][500],fx[15]={0,-1,-2,-2,-1,1,2,2,1},fy[15]={0,2,1,-1,-2,2,1,-1,-2};
queue< pair<int,int> > q;
bool go(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m&&bj[x][y]==0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void bfs(int x,int y,int b)
{
    a[x][y]=b;
    bj[x][y]=1;
    for(int i=1;i<=8;i++)
    {
        if(go(x+fx[i],y+fy[i]))
        {
            a[x+fx[i]][y+fy[i]]=b+1;
            q.push(make_pair(x+fx[i],y+fy[i]));
        }
        bj[x+fx[i]][y+fy[i]]=1;
    }
    while(!q.empty())
    {
        int zbx=q.front().first;
        int zby=q.front().second;
        q.pop();
        bfs(zbx,zby,a[zbx][zby]);
    }
}
int main()
{
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++)
    {
        for(int ii=1;ii<=m;ii++)
        {
            a[i][ii]=-1;
        }
    }
    bj[x][y]=1;
    bfs(x,y,0);
    for(int i=1;i<=n;i++)
    {
        for(int ii=1;ii<=m;ii++)
        {
            cout<<a[i][ii]<<"    ";
        }
        cout<<endl;
    }
}

by ___LuXun___ @ 2024-08-02 21:13:24

@Shanxiao520

#include<bits/stdc++.h>
using namespace std;
const int N=410;
int n,m;

struct str{
    int x,y;
}q[N*N];
int head=0,tail=1;
int v[N][N];
int dx[8]={1,1,2,2,-1,-1,-2,-2};
int dy[8]={2,-2,1,-1,-2,2,1,-1};
int sx,sy;
void bfs(){
    v[sx][sy]=0;
    q[1].x=sx;
    q[1].y=sy;
    while(head<tail){
        int xx=q[++head].x;
        int yy=q[head].y;
        int t=v[xx][yy];
        for(int i=0;i<8;i++){
            int nx=xx+dx[i];
            int ny=yy+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&v[nx][ny]==-1){
                v[nx][ny]=t+1;
                q[++tail].x=nx;
                q[tail].y=ny;
            }
        }
    }
}

int main(){
    cin>>n>>m>>sx>>sy;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v[i][j]=-1;
        }
    }
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%-5d",v[i][j]);
        }
        cout<<endl;
    }
    return 0;
}

抄吧

by hytallenxu @ 2024-08-02 21:13:53

@Shanxiao520

bj[x+fx[i]][y+fy[i]]=1;

注意到这里 x+\text{fx}_i 和 y+\text{fy}_i 可能会下标 -1。

by Terrible @ 2024-08-02 21:31:47

下面解释一下为什么提交中的越界会产生 RE（段错误）而本题反而没问题：

产生的原因是 [开不开 O2 数组排列方式不一样，故而越界的时候位置也不一样]。

我猜测你本地测试的时候是不开 O2 的，建议找方法在设置里打开。

洛谷提交的时候默认是开 O2 的，这个没问题，根据变量名出现顺序倒着排内存，所以 bj[-1][0] 是往最靠前的地方越界 2000 字节，很可能此时访问到了程序外的内存，被系统终止，出了段错误。

本地的时候没开 O2，根据变量名出现顺序顺着排内存，这时 bj[-1][0] 大概会越界到 a[500][5] 左右的位置。而且 n,m,x,y 位置靠后，是大概 bj[-1][500] 往前一点，由于 n\leqslant 400，所以没有被波及到。可见多开点没用的内存还是能减少 RE 的。

如果你在洛谷开 O2 提交时的变量顺序为：int n,m,x,y,bj[500][500],a[500][500]，那么就能 AC，原理自行分析。

by Terrible @ 2024-08-02 21:34:24

洛谷变量名称之间的大致位置关系

错字：本题× → 本地 √

by Shanxiao520 @ 2024-08-03 16:38:24

非常感谢各位大佬！抱歉没有及时回复，今天才看到消息

by Shanxiao520 @ 2024-08-03 16:47:52

@ LuXun @hytallenxu @Terrible

by Shanxiao520 @ 2024-08-06 08:08:29

@Terrible @hytallenxu @LuXun