目录
Description
输入格式
输出格式
输入样例
输出样例
Description
有一个N*M的格子迷宫,1代表该格子为墙,不能通过,0代表可以通过,另外,在迷宫中 有一些传送门,走到传送门的入口即会自动被传送到传送门的出口(一次传送算1步)。人在迷宫中可以尝试 上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口,以及起点和终点, 问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。
输入格式
该程序为多CASE,第1行为CASE的数量 每一个CASE,第1行为两个数N(行)和M(列) 然后N行每行M个数 之后是一个数W,为传送门的数量 之后每行一个传送门的入口坐标c1(行),r1(列)和出口坐标c2,r2 之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列) 注:传送门出入口和起点坐标和终点坐标不会出现在墙的位置 所有数字不超过100
输出格式
如题
输入样例
2 4 3 011 011 110 110 1 1 0 2 2 0 0 3 2 2 2 01 10 0 0 0 1 1
输出样例
3
die
题意:
在具有传送门的迷宫中求出从起点到终点的最短步数。
分析:
如果是普通迷宫,我们就可以直接用bfs模板即可,加了传送门后就稍微有点麻烦。但仔细分析也不难。我们只要每次先判断当前队头是否为传送门即可,如果为传送门,则走到传送门的出口并将其入队,如果不是,则按照模板走四个方向即可
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m,w,c1,r1,c2,r2,sc,sr,ec,er;
char g[N][N];//存储地图
int d[N][N];//存储第i行第j列的步数
PII door[N][N];//存储传送门的入口和出口
void bfs(){
memset(d,-1,sizeof(d));//初始化d为-1
queue<PII>q;
q.push({sc,sr});//将起点入队并将其步数初始化为0
d[sc][sr]=0;
PII t;
while(!q.empty()){
t=q.front();
//cout<<t.x<<' '<<t.y<<endl;
q.pop();
//判断当前位置是否为传送门
if(door[t.x][t.y].x!=-1&&door[t.x][t.y].y!=-1){
d[door[t.x][t.y].x][door[t.x][t.y].y]=d[t.x][t.y]+1;
//cout<<door[t.x][t.y].x<<' '<<door[t.x][t.y].y<<endl;
int xx=t.x,yy=t.y;
t.x=door[xx][yy].x;
t.y=door[xx][yy].y;
q.push(t);
continue;
}
//迷宫正常模板
int dir[4][2]={0,1,0,-1,1,0,-1,0};
for(int i=0;i<4;++i){
//cout<<t.x<<' '<<t.y<<endl;
int x=t.x+dir[i][0],y=t.y+dir[i][1];
if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]!='1'&&d[x][y]==-1){
//cout<<x<<' '<<y<<endl;
d[x][y]=d[t.x][t.y]+1;
q.push({x,y});
}
}
}
}
int main()
{
int kcase;
cin>>kcase;
while(kcase--){
for(int i=0;i<=100;++i){
for(int j=0;j<=100;++j){
door[i][j].x=-1;
door[i][j].y=-1;
}
}
cin>>n>>m;
for(int i=0;i<n;++i){
cin>>g[i];
getchar();
}
cin>>w;
for(int i=0;i<w;++i){
cin>>c1>>r1>>c2>>r2;
door[c1][r1].x=c2;
door[c1][r1].y=r2;
}
cin>>sc>>sr>>ec>>er;
bfs();
/*for(int i=0;i<4;++i){
for(int j=0;j<3;++j){
cout<<d[i][j]<<' ';
}
cout<<endl;
}*/
if(d[ec][er]==-1){
cout<<"die"<<endl;
}else{
cout<<d[ec][er]<<endl;
}
}
return 0;
}