3个AC，其余全RE，大佬求调T-T

_Seventeen_ @ 2024-12-24 00:24:19

#include<stdio.h>
int main(){
    int n,m,x,y;//x为行索引，y为列索引 
    int yy[8]={-2,-1,1,2,2,1,-1,-2};
    int xx[8]={-1,-2,-2,-1,1,2,2,1};
    scanf("%d %d %d %d",&n,&m,&x,&y);
    int lst[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            lst[i][j]=-1;
        }
    }
    int que[405*405][3];
    int p=0,top=0;
    que[top][0]=x-1;
    que[top][1]=y-1;
    que[top][2]=0;
    top++;
    while(p<top){
        int px=que[p][0],py=que[p][1];
        lst[px][py]=que[p][2];
        for(int i=0;i<8;i++){
            x=px+xx[i];
            y=py+yy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&lst[x][y]==-1){
                que[top][0]=x;
                que[top][1]=y;
                que[top][2]=que[p][2]+1;
                top++;
            }
        }
        p++;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            printf("%-5d",lst[i][j]);
        }
        printf("\n");
    }
    return 0;
} 

by postpone @ 2024-12-24 02:25:56

@Seventeen RE 说明越界了，我估计是你这个队列爆了，因为你这里的 bfs 不太对。

应该是在推进队列的时候就把值更新到地图上，而不是拿出来的时候再更新——否则可能一个点会被推进去很多次。

帮你改了一下，过了

#include <stdio.h>
int main() {
    int n, m, x, y; // x为行索引，y为列索引
    int yy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int xx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
    scanf("%d %d %d %d", &n, &m, &x, &y);
    int lst[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            lst[i][j] = -1;
        }
    }

    lst[x - 1][y - 1] = 0;

    int que[405 * 405][3];
    int p = 0, top = 0;
    que[top][0] = x - 1;
    que[top][1] = y - 1;
    que[top][2] = 0;
    top++;
    while (p < top) {
        int px = que[p][0], py = que[p][1];
        // lst[px][py] = que[p][2];
        for (int i = 0; i < 8; i++) {
            x = px + xx[i];
            y = py + yy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && lst[x][y] == -1) {
                lst[x][y] = que[p][2] + 1;
                que[top][0] = x;
                que[top][1] = y;
                que[top][2] = que[p][2] + 1;
                top++;
            }
        }
        p++;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%-5d", lst[i][j]);
        }
        printf("\n");
    }
    return 0;
}

by _Seventeen_ @ 2024-12-24 10:11:51

@postpone 后来我自己也想到了，但还是感谢