求助玄关
  • 板块灌水区
  • 楼主hkl99
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/14 19:28
  • 上次更新2024/12/14 21:42:44
查看原帖
求助玄关
770439
hkl99楼主2024/12/14 19:28

Olya and Energy Drinks

我写了一个 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;
}
2024/12/14 19:28
加载中...