大佬帮帮我啊,实在不知道哪里出了问题
查看原帖
大佬帮帮我啊,实在不知道哪里出了问题
272820
PureJoy楼主2021/2/17 23:17
/*
我的思路是:考虑从当前点出发能到达的4个点,有以下几种情况:
	(1)可能下一步踩在草地上,正常将其加入队列即可,并修改下一步踩上的点的ans为当前点的ans+1,并把这块草地标记为$(已经走过);
	(2)可能下一步踩在假的传送门上,和正常草地一样处理;
	(3)可能下一步踩在真的传送门上,那么修改下一步踩上的点的ans为当前点的ans+1,并修改对应传送门的ans为当前点的ans+1,将传送门的另一端加入队列。
以上做法对应的几个坑点:
	(1)传送门可能多次经过,所以走过传送门不将其标记为$;
	(2)传送门一旦踩上必定会触发,所以门的两头时间相同,且要将门的另一头加入队列;
	(3)传送门如果只是中转站的话,不能传过去马上传回来,必须在门的另一头先踩一下草地再上传送门传回来。比如门的另一端被墙包围着,那么传过去就回不来了。
	   由于我考虑的是当前点能到达的四个点的情况,所以不会出现传过去立刻传回来的情况。
*/
#include <stdio.h>
#include <iostream>
#include <queue>
#define maxn 305
using namespace std;

char p[maxn][maxn];	//p用来存放地图
int n,m,ans[maxn][maxn]={};//n,m未地图大小,ans是到地图每个点的最短时间
int q[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//上下左右偏移量
int door[26][4]={};//用两组坐标来记录26个可能存在的传送装置,初始化未0
struct coord{
	int x,y;
};
queue <coord> Q;//bfs用到的队列

int main(){
	//freopen("P1825_6.in","r",stdin);
	int start_x,start_y,end_x,end_y;//起点和终点的坐标
	scanf("%d%d",&n,&m);
	getchar();
	for(int i=1;i<=n;++i)		//读入图并进行预处理
		for(int j=1;j<=m+1;++j){
			scanf("%c",&p[i][j]);
			if('A'<=p[i][j] && p[i][j]<='Z'){	//记录传送装置
				if(door[p[i][j]-'A'][0]==0){
					door[p[i][j]-'A'][0]=i;
					door[p[i][j]-'A'][1]=j;
				}else{
					door[p[i][j]-'A'][2]=i;
					door[p[i][j]-'A'][3]=j;
				}
			}else if(p[i][j]=='@'){		//记录起点
				start_x=i; start_y=j;
			}else if(p[i][j]=='='){		//记录终点
				end_x=i; end_y=j;
			}
		}
		
	Q.push(coord{start_x,start_y});//开始bfs,将起点加入队列
	p[start_x][start_y]='$';	//并将其标记为$,表示已经走过
	while(!Q.empty()){
		coord now=Q.front();
		Q.pop();
		//printf("%d %d %d\n",now.x,now.y,ans[now.x][now.y]);
		if(now.x==end_x && now.y==end_y){	//如果到达终点就输出终点的答案
			printf("%d",ans[now.x][now.y]);
			return 0;
		}
		for(int i=0;i<4;++i){	//依次遍历4个点
			int xx=now.x+q[i][0],yy=now.y+q[i][1];//下一步的坐标
			if(xx>=1 && yy>=1 && xx<=n && yy<=m && p[xx][yy]!='#' && p[xx][yy]!='$'){//如果下一步没出界且不是墙且没经过,就考虑加入队列
				char temp=p[xx][yy];//先统一标记为$
				p[xx][yy]='$';
				ans[xx][yy]=ans[now.x][now.y]+1;//下一步的时间为当前位置时间+1
				if('A'<=temp && temp<='Z' && door[temp-'A'][0]*door[temp-'A'][1]*door[temp-'A'][2]*door[temp-'A'][3] !=0){
				//如果是传送门且是真传送门(地图坐标均为正整数,如果乘积为0必然是假门)
					if(door[temp-'A'][0]==xx && door[temp-'A'][1]==yy){	//先判断是门的哪一头
						Q.push(coord{door[temp-'A'][2],door[temp-'A'][3]});//将传送门的另一端加入队列。
						ans[door[temp-'A'][2]][door[temp-'A'][3]]=ans[xx][yy];//修改对应的时间为这一头的时间(这一头的门的时间前面统一改过了)
					}else{
						Q.push(coord{door[temp-'A'][0],door[temp-'A'][1]});
						ans[door[temp-'A'][0]][door[temp-'A'][1]]=ans[xx][yy];
					}
					p[xx][yy]=temp; //由于传送门可以经过多次,所以还原
				}else{
					Q.push(coord{xx,yy});//如果不是门就加入队列继续搜即可,时间已经改过了,也已经标记为$了
				}
			}
		}
	}
}
2021/2/17 23:17
加载中...