78分求助,有注释
查看原帖
78分求助,有注释
510555
ImposterAnYu楼主2023/8/16 11:57
#include<bits/stdc++.h>
#define N 1000
#define M 1000000
#define int1 int
using namespace std;
int1 n,m,nm,i,j,k,bs,bh[N + 5][N + 5],ta[M + 5],pre[M + 5],to[M + 5],w[M + 5],dis[M + 5],st,en,dx[4] = {1,-1},dy[4] = {0,0,1,-1},zj[N + 5][N + 5];
char ch[N + 5][N + 5];
bool vis[N + 5][N + 5];
struct owo{
	int1 x,y,st;
};
struct qaq{//自定义比较结构体,在priority_queue中st小的排在前面 
	bool operator()(const owo &x,const owo &y){
		return x.st > y.st;
	}
};
priority_queue<owo,vector<owo>,qaq> qu;
priority_queue<pair<int1,int1>,vector<pair<int1,int1> >,greater<pair<int1,int1> > > q;
void C(){//关同步流,加速读写 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	return ;
}
void add_edge(int1 x,int1 y,int1 z){//链式前(后)向星存边 
	pre[++bs] = ta[x],ta[x] = bs,to[bs] = y,w[bs] = z;
	return ;
}
bool yq(int1 x,int1 y,int1 z){//判断该点的某一方向上的相邻位置有没有墙 
	if(ch[x + dx[z]][y + dy[z]] == '#'){
		return 1;
	}
	return 0;
}
void dijkstra(int1 x,int1 n){//堆优化dijkstra 
	for(int1 i = 1; i <= n; i++){
		dis[i] = 1145141919;
	}
	dis[x] = 0;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int1 r = q.top().second;
		q.pop();
        for(int1 i = ta[r]; i; i = pre[i]){
			int1 v = to[i],d = dis[r] + w[i];
			if(dis[v] > d){
				dis[v] = d;
				q.push(make_pair(dis[v],v));
			}
		}
	}
	return ;
}
int main(){
	C();
	cin >> n >> m;
	nm = n * m;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){//读入 
			cin >> ch[i][j];
			bh[i][j] = (i - 1) * m + j;//给每个点一个唯一的编号 
			if(ch[i][j] == 'C'){//起点 
				ch[i][j] = '.';
				st = bh[i][j];
			}
			if(ch[i][j] == 'F'){//终点 
				ch[i][j] = '.';
				en = bh[i][j];
			}
		}
	}
	for(i = 1; i <= n; i++){//相邻的点之间建边 
		for(j = 1; j <= m; j++){
			if(ch[i][j] == '.'){
				for(k = 0; k <= 3; k++){
					int1 x = i + dx[k],y = j + dy[k];
					if(ch[x][y] == '.'){
						add_edge(bh[i][j],bh[x][y],1);
					}
				}
				zj[i][j] = 1145141919;//初始化(?) 
			}else{
				qu.push((owo){i,j,0});//将墙入队 
				vis[i][j] = 1;
			}
		}
	}
	while(!qu.empty()){//算每个点与最近的墙的距离 
		owo now = qu.top();
		qu.pop();
		for(i = 0; i <= 3; i++){
			int1 x = now.x + dx[i],y = now.y + dy[i],s = now.st + 1;
			if(min(x,y) >= 1 && x <= n && y <= m && !vis[x][y]){
				zj[x][y] = s,vis[x][y] = 1;
				qu.push((owo){x,y,s});
			}
		} 
	}
	for(i = 1; i <= n; i++){//建传送的边 
		for(j = 1; j <= m; j++){
			if(ch[i][j] == '.'){
				for(k = i + 1; k <= n; k++){
					if(ch[k][j] == '.'){
						if(yq(k,j,0)){
							add_edge(bh[i][j],bh[k][j],zj[i][j]);
							break;
						}
					}else{
						break;
					}
				}
				for(k = i - 1; k >= 1; k--){
					if(ch[k][j] == '.'){
						if(yq(k,j,1)){
							add_edge(bh[i][j],bh[k][j],zj[i][j]);
							break;
						}
					}else{
						break;
					}
				}
				for(k = j + 1; k <= m; k++){
					if(ch[i][k] == '.'){
						if(yq(i,k,2)){
							add_edge(bh[i][j],bh[i][k],zj[i][j]);
							break;
						}
					}else{
						break;
					}
				}
				for(k = j - 1; k >= 1; k--){
					if(ch[i][k] == '.'){
						if(yq(i,k,3)){
							add_edge(bh[i][j],bh[i][k],zj[i][j]);
							break;
						}
					}else{
						break;
					}
				}
			}
		}
	}
	dijkstra(st,nm);//跑最短路 
	if(dis[en] == 1145141919){//无解 
		cout<< "nemoguce" << endl;
	}else{
		cout<< dis[en] << endl;
	}
	return 0;
}
2023/8/16 11:57
加载中...