9RE 1WA求助
查看原帖
9RE 1WA求助
127925
Kio_楼主2020/8/14 17:03

蒟蒻刚学的A*,但是不知道为什么本地能运行,上评测机就RE了......

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//void read()
//{
//	char c='0';
//	while(c=='0'||c=='1')
//	{
//		scanf("%c",&c);
//		m[xn][ynn]=c-'0';
//		ynn++;
//	}
//}
int n,x1,y11,x2,y2;//因为不知道什么原因,写y1过不了本地编译,就写成y11了=-= 

struct pt
{
	int x,y,num;
}queue[8000100];

int juli(int a,int b,int c,int d)
{
	return sqrt( (a-c)*(a-c) + (b-d)*(b-d) ) + 1;//+1是为了避免精度误差,因为返回的是int型 
}

int r=1;//队列的最右端 
int dr=1;//当前的队列位置 
int num;
double dis;
bool m[1010][1010];

bool pd(int x,int y)//判断 
{
	if(m[x][y]==1)return 0;
	if(x==0||x==n+1)return 0;
	if(y==0||y==n+1)return 0;
	return 1;
}
int main()
{
	scanf("%d",&n);
	string a;
	
	for(int i=1;i<=n;i++){
		cin>>a;
		for(int j=1;j<=n;j++)
		{
			m[i][j]=a[j-1]-'0';
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++)printf("%d ",m[i][j]);
//		printf("\n");
//	}
//	return 0;
//}
	scanf("%d %d %d %d",&x1,&y11,&x2,&y2);	
	memset(queue,0,sizeof(queue));
	dis=juli(x1,y11,y2,y2);
	queue[1].x=x1;
	queue[1].y=y11;

	while(queue[dr].x!=x2&&queue[dr].y!=y2)
	{
		while(juli(queue[dr].x, queue[dr].y, x2, y2) > dis) dr++;//若搜索到的点距离大于x1y1~x2y2的距离,就跳过 
		for(int i=1;i<=4;i++)
		{
			if(pd(queue[dr].x + dx[i-1], queue[dr].y + dy[i-1]))//若可走 
			{
				queue[r+1].x = queue[dr].x + dx[i-1];
				queue[r+1].y = queue[dr].y + dy[i-1];
				queue[r+1].num = queue[dr].num + 1;
				m[queue[dr].x][queue[dr].y] = 1;
				r++;
			}
		}
		dr++;
	}
	printf("%d",queue[dr].num+1);
	return 0;
}

求大佬指点QwQ

2020/8/14 17:03
加载中...