30分，7MLE，求救

zhou_yihe @ 2024-08-19 14:31:45

#include<bits/stdc++.h>
using namespace std;

struct node{
    int x;
    int y;
    int step;
};

int a[401][401];
int dx[8]={2,2,-2,-2,1,1,-1,-1};
int dy[8]={1,-1,1,-1,2,-2,2,-2};
int n,m;

bool check(int x,int y){
    return x>=1 && x<=n && y>=1 && y<=m && a[x][y]==-1;
}

void bfs(int sx,int sy){
    queue<node> q;
    q.push({sx,sy,0});
    while(!q.empty()){
        node tmp=q.front();
        q.pop();
        a[tmp.x][tmp.y]=tmp.step;
        for(int i=0;i<8;i++){
            int nx=tmp.x+dx[i];
            int ny=tmp.y+dy[i];
            if(check(nx,ny)){
                q.push({nx,ny,tmp.step+1});
            }
        }
    }
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int sx,sy;
    cin>>n>>m>>sx>>sy;
    memset(a,-1,sizeof(a));

    bfs(sx,sy);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%-5d",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

by zhou_yihe @ 2024-08-19 14:32:06

悬棺

by Emil_ @ 2024-08-19 14:35:30

@zyc_always_AC

ac代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,q[160010][3],d[410][410];
int fx[9]={0,-2,-1,1,2,2,1,-1,-2};
int fy[9]={0,1,2,2,1,-1,-2,-2,-1};
signed main(){
    cin>>n>>m>>x>>y;
    memset(d,-1,sizeof(d));
    int head=1,tail=1;
    q[1][1]=x;
    q[1][2]=y;
    d[x][y]=0;
    while(head<=tail){
        int tx,ty;
        for(int i=1;i<=8;i++){
            tx=q[head][1]+fx[i];
            ty=q[head][2]+fy[i];
            if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&d[tx][ty]==-1){
                tail++;
                q[tail][1]=tx;
                q[tail][2]=ty;
                d[tx][ty]=d[q[head][1]][q[head][2]]+1;
            }
        }
        head++;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<left<<setw(5)<<d[i][j];
        cout<<endl;
    }
    return 0;
} 

求关

by _WhiteDeer_ @ 2024-08-19 14:36:34

@zyc_always_AC 要不用个vis数组去重试试看呢？感觉你这个好像是队列MLE了。

by zhou_yihe @ 2024-08-19 14:41:16

@Emil_ 已关

by zhou_yihe @ 2024-08-19 14:52:49

@lccjsw 只关一个

本帖结

by _WhiteDeer_ @ 2024-08-19 14:56:22

@zyc_always_AC 等一下，我发现你代码有个问题。你查找到该点未访问过就应该直接赋值，而不是放进队列后再赋值，不然你会重点（就是队列里面有好多一样的点）导致MLE爆队列。

by lg128 @ 2024-08-21 12:34:01

@WhiteDeer 感谢！读了好几遍这句话，终于看懂了