#4、#7WA,检查不出来问题,有人能指个方向吗?
查看原帖
#4、#7WA,检查不出来问题,有人能指个方向吗?
298051
xkcdjerry楼主2020/7/12 21:30

窝写了一个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;
}
2020/7/12 21:30
加载中...