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……