Kio_ @ 2020-08-14 17:03:05
蒟蒻刚学的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
by Kio_ @ 2020-08-14 17:19:02
为什么没有人啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
TAT