#4、#7WA,检查不出来问题,有人能指个方向吗?

P1746 离开中山路

xkcdjerry @ 2020-07-12 21:30:22

窝写了一个bfs爆搜,AC8个点,WA两个,本地怎么都调不出来问题,有哪位巨佬帮助吗(窝试过queue了,貌似不是手写队列的原因QAQ)
记录:https://www.luogu.com.cn/record/35086946
代码:

#include <cstdio>
#define N 1010
int n;
int vis[N][N];
struct point
{
    int x,y,dis;
};
struct queue
{
    point a[N*N];
    int head=0,tail=0;//绝对不会满,所以不特判
}q;
point pop()
{
    point val=q.a[q.tail++];
    q.tail%=n;
    return val;
}
void push(point val)
{
    q.a[q.head++]=val;
    q.head%=n;
}
inline bool read_1()
{
    char ch;
    for(ch=getchar();ch!='1'&&ch!='0';ch=getchar())
        ;
//  puts("READ!");
    return ch=='1';
}
inline void add(int x,int y,int dis)
{
    point p;
    p.x=x;p.y=y;p.dis=dis;
    push(p);
}

int work(int x1,int y1,int x2,int y2)
{
    int dx[]={ 0, 0, 1,-1};
    int dy[]={ 1,-1, 0, 0};
    add(x1,y1,0);
    while(1)
    {
        point p=pop();
//      printf("PROCESSING: %d %d %d %d\n",q.tail-1,p.x,p.y,p.dis);
        for(int i=0;i<4;i++)
        {
            int x=p.x+dx[i],y=p.y+dy[i];
            if(x>0&&x<=n&&y>0&&y<=n&&\
                    vis[x][y]==false)
            {
//              printf("???%d???\n",(int)vis[x][y]);
                if(x==x2&&y==y2) return p.dis+1;
                vis[x][y]=true;
                add(x,y,p.dis+1);
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            vis[i][j]=read_1();
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    printf("%d",work(x1,y1,x2,y2));
    return 0;
}

by WanderingTrader @ 2020-07-12 22:23:18

33行可以搞定的水题被你写了73行


by xkcdjerry @ 2020-07-15 22:28:59

@zycany 您聚呀,33行就写出来叻…… 我不会写A* wtcl


by xkcdjerry @ 2020-07-15 22:29:19

膜一膜QAQ


by WanderingTrader @ 2020-07-15 22:35:34

@xkcdjerry 这不是A* ,这是BFS模板


by WanderingTrader @ 2020-07-15 22:36:00

@xkcdjerry 我也不会A* 我更蒟蒻


by xkcdjerry @ 2020-07-15 22:38:41

您红名,一定是聚佬 %%%
(话说这个BFS模板哪里有问题呀,看起来就是一个板子题,就是写不对 抓狂


by xkcdjerry @ 2020-07-15 22:39:21

窝还是滚回去用模拟退火8……


|