题解 | #maze#

展示一下我缝缝补补的艰难过程吧，刚开始没有考虑到一个点可以有多个传送门的情况，然后一直33.3%通过率，发现以后改成三维vector数组来存传送门的终点和起点。发现还是WA，网上查了优先队列的资料发现，他的排序方式和sort不一样，sort想要升序排列，需要step<a.step;,但是**优先队列要升序排需要step>a.step;**就这两个小细节WA了一个半小时几乎，还有就是读题的时候没读完，漏了下标从0开始 （@_@）

补充一点，无论是优先队列还是普通队列，先到达某一个点的路径一定是最短的，值得好好思考一下为什么优先队列的路径也是先到的是最短的，因为路径小的本来就排在队列前面。

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n, m, q;
const int M = 305;
char mp[M][M];
int sx, sy, tx, ty;
//struct node{
//	int x1,x2,y1,y2;
//}a[1005];
int cnt = 0;
struct p {
	int x, y, step;
	p(int a, int b, int c) { x = a; y = b; step = c; }
	p() {}
	bool operator<(const p& a)const {
		return step > a.step;
	}
};
int vis[M][M];
//int pos[M][M];
priority_queue<p> s;
int mov[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
bool check(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y <m;
}
struct node {
	int x, y;
	node(int a, int b) {
		x = a;
		y = b;
	}
	node(){}
};
vector<node> ve[M][M];
void bfs() {
	while (!s.empty()) {
		p tmp = s.top();
		s.pop();
	//	cout << tmp.x << " " << tmp.y << endl;
		if (tmp.x == tx && tmp.y == ty) {
			cout << tmp.step<<endl;
			return;
		}
		for (int i = 0; i < ve[tmp.x][tmp.y].size(); i++) {
			if (vis[ve[tmp.x][tmp.y][i].x][ve[tmp.x][tmp.y][i].y]) continue;
			s.push(p(ve[tmp.x][tmp.y][i].x, ve[tmp.x][tmp.y][i].y, tmp.step + 3));
		}
		for (int i = 0; i < 4; i++) {
			int xx = tmp.x + mov[i][0]; int yy = tmp.y + mov[i][1];
			if (check(xx, yy) && !vis[xx][yy] && mp[xx][yy] != '#') {
				vis[xx][yy] = 1;
				//if (pos[xx][yy]) {
				//	int cx = cun[xx][yy].cx;
				//	int cy = cun[xx][yy].cy;
				//	if (!vis[cx][cy]) {
				//		//vis[cx][cy] = 1;
				//		s.push(p(cx, cy, tmp.step + 4));
				//	}
				//}
				s.push(p(xx, yy, tmp.step + 1));
			}
		}
	}
	cout << "-1" << endl;
	return;
}

int main() {
	while (cin >> n >> m >> q) {
		memset(vis, 0, sizeof(vis));
	//	memset(pos, 0, sizeof(pos));
		memset(mp, 0, sizeof(mp));
		
		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;
				//	cout << i << " " << j << endl;
				}
				if (mp[i][j] == 'T') {
					tx = i; ty = j;
				}
				ve[i][j].clear();
			}
		}

		for (int i = 1; i <= q; i++) {
			int x1, x2, y1, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			if (mp[x1][y1] == '#' ||mp[x2][y2]=='#')	continue;
			//			a[++cnt].x1=x1; a[cnt].y1=y1; a[cnt].x2=x2; a[cnt].y2=y2;
			//pos[x1][y1] = 1;
			ve[x1][y1].push_back(node(x2,y2));
		}
		vis[sx][sy] = 1;
		while (!s.empty()) { s.pop(); }
		/*if (pos[sx][sy]) {
			int xx = cun[sx][sy].cx;
			int yy = cun[sx][sy].cy;
			s.push(p(xx,yy,3));
			s.push(p(sx, sy, 0));
		}
		else*/
		s.push(p(sx, sy, 0));
		bfs();

	}
	return 0;
}