Description

小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。

小明只能向上下左右相邻的格子移动，每移动一次花费1秒。

有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。

一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。

Solution

经典的bfs问题，但是多出了一个传送阵，能够花费3s的时间从入口到出口
于是不能用普通的bfs的队列去做，因为最快到达的不一定花费时间最短
那么我们可以考虑取一个优先队列，每次我们都取当前花费时间最短的点去更新
这样的话就能保证最快到达终点的点是时间最短的
另外要注意这里输入的坐标 是
习惯数组从1开始的同学记得先 ++, ++
传送阵的话可以用一个 来存
一开始要把起点(和起点的所有传送出口)都放进队里

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll mod = 1e9 + 7;
const int N = 2e5 + 5;

char maze[305][305];
int dist[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
struct node {
  int x, y, step;
  node(int _x = 0, int _y = 0, int _step = 0): x(_x), y(_y), step(_step){}
  bool operator < (const node &s) const {
    return step > s.step;
  }
};
int sx, sy, ex, ey, n, m, qu;
bool vis[305][305];
vector<pair<int, int> > G[305][305];

int bfs() {
  priority_queue<node> q;
  q.push(node(sx, sy, 0));
  for(int i = 0; i < G[sx][sy].size(); i++) {
    int lx = G[sx][sy][i].first, ly = G[sx][sy][i].second;
    if(!vis[lx][ly] && maze[lx][ly] != '#' && lx >= 1 && lx <= n && ly >= 1 && ly <= m) {
      q.push(node(lx, ly, 3));
    } 
  }
  while(!q.empty()) {
    node now = q.top();
    q.pop();
    if(vis[now.x][now.y]) continue;
    vis[now.x][now.y] = 1;
    //cout << now.x << ' ' << now.y << "\n";
    if(now.x == ex && now.y == ey) return now.step;
    for(int i = 0; i < 4; i++) {
      int xx = now.x + dist[i][0];
      int yy = now.y + dist[i][1];
      if(!vis[xx][yy] && maze[xx][yy] != '#' && xx >= 1 && xx <= n && yy >= 1 && yy <= m) {
        for(int j = 0; j < G[xx][yy].size(); j++) {
          int lx = G[xx][yy][j].first, ly = G[xx][yy][j].second;
          if(!vis[lx][ly] && maze[lx][ly] != '#' && lx >= 1 && lx <= n && ly >= 1 && ly <= m) {
            q.push(node(lx, ly, now.step + 4));
          } 
        }
        q.push(node(xx, yy, now.step + 1));
      }
    }
  }
  return -1;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  while(cin >> n >> m >> qu) {
    //cin >> n >> m >> qu;
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= m; j++) {
        G[i][j].clear(), vis[i][j] = 0;
      }
    }
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= m; j++) {
        cin >> maze[i][j];
        if(maze[i][j] == 'S') {
          sx = i, sy = j;
        }
        if(maze[i][j] == 'T') {
          ex = i, ey = j;
        }
      }
    }
    while(qu--) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      x1++, y1++, x2++, y2++;
      G[x1][y1].push_back({x2, y2});
    }
    cout << bfs() << "\n";
  }
  return 0;
}