A*求助
查看原帖
A*求助
670766
QWQ_SenLin楼主2022/10/20 22:17

WA了一个点,求调。

#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;

int L , R , C , qx , qy , qz , zx , zy , zz;
int mapp[35][35][35];
int vis[35][35][35];
int dis[10][5] = {{1 , 0 , 0} , {-1 , 0 , 0} , {0 , 1 , 0} , {0 , -1 , 0} , {0 , 0 , 1} , {0 , 0 , -1}};

struct QWQ{
	int x , y , z , g;
	bool operator < (QWQ x) const{
		return x.g < g;
	}
};

int get_g(int x , int y , int z){
	return abs(zx - x) + abs(zy - y) + abs(zz - z) * 10;
}

void bfs(){
	priority_queue <QWQ> q;
	q.push((QWQ){qx , qy , qz , 0});
	while(!q.empty()){
		QWQ t = q.top();
		q.pop();
		if(t.x == zx && t.y == zy && t.z == zz){
			printf("Escaped in %d minute(s).\n" , vis[t.x][t.y][t.z]);
			return ;
		}
		for(int i = 0;i < 6;i++){
			int x = t.x + dis[i][0];
			int y = t.y + dis[i][1];
			int z = t.z + dis[i][2];
			if(x <= 0 || y <= 0 || z <= 0 || x > R || y > C || z > L)
				continue;
			if(vis[x][y][z] || (x == qx && y == qy && z == qz)) 
				continue;
			if(mapp[x][y][z]) continue;
			vis[x][y][z] = vis[t.x][t.y][t.z] + 1;
			q.push((QWQ){x , y , z , get_g(x , y , z)});
			// printf("%d %d %d\n" , x , y , z);
		}
	}
	puts("Trapped!");
}

int main(void){
	// freopen("qwq.in" , "r" , stdin);
	scanf("%d%d%d" , &L , &R , &C);
	for(int i = 1;i <= L;i++){
		for(int j = 1;j <= R;j++){
			char s[35];
			scanf("%s" , s + 1);
			for(int z = 1; z <= C;z++){
				if(s[z] == '#') mapp[j][z][i] = 1;
				if(s[z] == 'S'){
					qx = j;
					qy = z;
					qz = i;
				}
				if(s[z] == 'E'){
					zx = j;
					zy = z;
					zz = i;
				}
			}	
		}
	}

	// for(int i = 1;i <= L;i++){
	// 	for(int j = 1;j <= R;j++){
	// 		for(int z = 1; z <= C;z++)
	// 			printf("%d " , mapp[j][z][i]);
	// 		puts("");
	// 	}
	// 	puts("\n");
	// }
	bfs();
}
2022/10/20 22:17
加载中...