58分蒟蒻,救救孩子吧!
查看原帖
58分蒟蒻,救救孩子吧!
290570
UnderDogStar楼主2020/5/6 23:05
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue> 
#define MaxN 310
using namespace std;
struct Node{
	int x,y,step;
	Node(int newx,int newy,int newstep){
		x=newx,y=newy,step=newstep;
	}
};
char maps[MaxN][MaxN];
bool jud[MaxN][MaxN];
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}},n,m; 
void change(int &x,int &y){		
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			if( maps[i][j] == maps[x][y] && !jud[i][j] ){//寻找传送门,并利用jud判断是否是走过的传送门 
				x=i;y=j;
				break;
			}	
	jud[x][y]=true; 
}
void Bfs(int sx,int sy,int dx,int dy){
	queue <Node> q;
	q.push(Node(sx,sy,0));
	jud[sx][sy]=true;
	while( !q.empty() ){
		Node head=q.front();
		q.pop();
		if( head.x == dx && head.y == dy ){
			cout<<head.step<<endl;
			break;
		}
		if( isalpha(maps[head.x][head.y]) )//是字母的话说明是传送门 
			change(head.x,head.y); 
		for(int i=0; i<4; i++){//搜索 
			int newx=head.x+dir[i][0];
			int newy=head.y+dir[i][1];
			//判断 是否越界 是否会走到玉米 是否走过 
			if( newx >= 0 && newx < n && newy >= 0 && newy < m && maps[newx][newy]!='#' && !jud[newx][newy]){
				q.push(Node(newx,newy,head.step+1));//将符合要求的放入队列 
				jud[newx][newy]=true;
			}
		}
	}
	return ;
}
int main(){
	cin>>n>>m;
	int sx,sy,dx,dy;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++){
			cin>>maps[i][j];
			if( maps[i][j] == '@' ){//起点 
				sx=i;sy=j;
			}
			if( maps[i][j] == '=' ){//终点 
				dx=i;dy=j;
			}
		} 
	Bfs(sx,sy,dx,dy);
	return 0;
} 
2020/5/6 23:05
加载中...