我写了一个 A* 算法为啥写挂了,测的样例都是对的,但是提交到另一个OJ(机构的OJ,原题)上全部输出-1,自己也造了几个样例也对了,有大佬帮忙看看错哪了吗
代码:
#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
const int N=1010;
int n,sx,sy,ex,ey,m,k,fx[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
char a[N][N];
bool vis[N][N],flag=true,vvis[N][N];
struct node {
int f,x,y,g,h;
bool operator <(const node &a)const {
return a.f<f;
}
};
priority_queue<node>q;
int jl(int x,int y,int nx,int ny) {
return abs(x-nx)/k+abs(y-ny)/k;
}
int Astar() {
vis[sx][sy]=true;
node t;
t.x=sy;
t.y=sy;
t.g=0;
t.h=jl(sx,sy,ex,ey);
t.f=t.g+t.h;
q.push(t);
while(!q.empty()) {
t=q.top();
q.pop();
//print(t.x,t.y,t.g+1);
vvis[t.x][t.y]=true;
for(int j=0; j<4; j++) {
for(int i=1; i<=k; i++) {
node tt;
tt.x=t.x+fx[j][0]*i;
tt.y=t.y+fx[j][1]*i;
if(tt.x==ex&&tt.y==ey) {
printf("%d",t.g+1);
flag=false;
return 0;
}
if(tt.x>=1&&tt.y>=1&&tt.x<=n&&tt.y<=m&&a[tt.x][tt.y]=='.'&&vis[tt.x][tt.y]==false) {
if(tt.x==ex&&tt.y==ey) {
printf("%d",t.g+1);
flag=false;
return 0;
}
vis[tt.x][tt.y]=true;
tt.g=t.g+1;
tt.h=jl(tt.x,tt.y,ex,ey);
tt.f=tt.g+tt.h;
q.push(tt);
}
if(a[tt.x][tt.y]=='#') {
goto hr;
}
}
hr:
;
}
}
return 0;
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
scanf("%c",&a[i][j]);
while(1) {
if(a[i][j]!='\n') {
break;
}
scanf("%c",&a[i][j]);
}
}
}
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
Astar();
if(flag) {
printf("-1");
}
return 0;
}