目录

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为-1queue<PII>q;q.push({sc,sr});//将起点入队并将其步数初始化为0d[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;
}