输入描述:

有多组数据。对于每组数据：
第一行有三个整数n,m,q(2≤ n,m≤300,0≤ q ≤ 1000)。
接下来是一个n行m列的矩阵，表示迷宫。
最后q行，每行四个整数x1,y1,x2,y2(0≤ x1,x2< n,0≤ y1,y2< m)，表示一个传送阵的入口在x1行y1列，出口在x2行y2列。

输出描述:

如果小明能够活着到达目的地，则输出最短时间，否则输出-1。

#include<bits/stdc++.h>
using namespace std;
const int N = 303;
char mp[N][N];//迷宫
int visit[N][N];//判断是否走过，1走过，0未走 
int Qx[N];//传送门 x坐标
int	Qy[N];//传送门y坐标 
int n,m;//迷宫：n行，m列 
int q;//传送门个数 
//左下右上四个方位 
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct Time
{
	int x;
	int y;
	int time;
};
 
int bfs(int sx,int sy,int ex,int ey)
{
	queue<Time>qu;//结构型队列
	if(mp[sx][sy]=='#') return -1;//起点为陷阱 
	qu.push(Time{sx,sy,0});//最初，小明在sx,sy处，所用时间为0 
	while(!qu.empty())
	{
		Time s = qu.front();
		 qu.pop();//出队
		if(s.x==ex&&s.y==ey)
		{
			return s.time;//如果到达终点则返回所用时间 
		} 
			Time next;//下一个位置
				     //要么走传送门，走传送门要注意 终点是否为陷阱 
		 	         //接下来有两种选择，要么上下左右走
		 	if(Qx[s.x]!=-1&&Qy[s.y]!=-1&&mp[Qx[s.x]][Qy[s.y]]!='#'
			 &&visit[Qx[s.x]][Qy[s.y]]==0&&mp[s.x][s.y]!='#')//第一种 
																//如果不为-1那么这个位置肯定有传送门,
			{													//再判断 出口是否为陷阱,
																//再判断是否走过 
															//由于传送们的坐标肯定在迷宫内，则不需要判断越界 
				// 下一个坐标就是传送门的终点 
				next.x = Qx[s.x];
				next.y = Qy[s.y];
				next.time = s.time + 3; 
				visit[next.x][next.y] = 1;//走过 
				qu.push(next);
			} 
			
		 for(int i=0;i<4;i++)
		 {
		 
			//上第二种，下左右走 
			
				next.x = s.x + dx[i];
				next.y = s.y + dy[i];
				next.time = s.time + 1; 
			//首先判断是否越界 或者是否是陷阱 
			   if(next.x<0||next.x>n||next.y<0||next.y>m||mp[next.x ][next.y]=='#') continue;
			  //再判断是否走过 
			   if(visit[next.x][next.y ]==1) continue; 	
			   visit[next.x][next.y] = 1;
			   qu.push(next);
			
		 } 
		
	 //	cout<<"a"<<endl; 
		 
	} 
	return -1;//无法走到终点 
}
int main()
{
	while(cin>>n>>m>>q) //多组出入 
	{
			int sx,sy;//起点
	   		int ex,ey;//终点 
	//输入迷宫 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]=='S') 
			{
				sx = i;
				sy = j;//记录起点坐标 
			} 
			 if(mp[i][j]=='T')
			 {
			 	ex = i;
			 	ey = j;//记录终点坐标 
			 } 
		}
	}
	//输入传送门位置
	int qsx,qsy;//传送门 起点坐标
	int qex,qey;//传送门终点坐标 
	memset(visit,0,sizeof(visit));//利用memset函数，全部标记为0，表示为走过
	memset(Qx,-1,sizeof(Qx)); 
	memset(Qy,-1,sizeof(Qy)); 
	
	for(int i=1;i<=q;i++)//输入传送门 
	{
	 	cin>>qsx>>qsy>>qex>>qey;
	    Qx[qsx] = qex; 
	    Qy[qsy] = qey;//表示从点（qsx,qsy）通向点（qex,qey） 
	} 
	visit[sx][sy] = 1;//起点当然走过啦 
	int ans = bfs(sx,sy,ex,ey);//调用函数，进行bfs操作 
	cout<<ans<<endl;	
	}
	return 0;
}