NC15665 maze

题目地址：

https://ac.nowcoder.com/acm/problem/15665

基本思路：

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 310;
int n,m,q,d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
char a[maxn][maxn];
bool vis[maxn][maxn];
int dp[maxn][maxn];
map<pii,vector<pii>> memo;
pii star,ed;
int bfs(){
  mset(dp,INF);
  mset(vis,false);
  queue<pii> que;
  dp[star.first][star.second] = 0;
  que.push(star);
  while(!que.empty()){
    int x = que.front().first,y = que.front().second;
    que.pop();
    vis[x][y] = false;//vis数组是用来防止重复入队的;
    if(memo.count({x,y})) {
      for(auto it : memo[{x,y}]) {//传送门的情况;
        int nx = it.first, ny = it.second;
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && !vis[nx][ny]) {
          if (dp[x][y] + 3 <= dp[nx][ny]) {
            dp[nx][ny] = min(dp[nx][ny], dp[x][y] + 3);
            vis[nx][ny] = true;
            que.push({nx, ny});
          }
        }
      }
    }
    for(int i = 0 ; i < 4 ; i++){//直接走的情况;
      int nx = x + d[i][0],ny = y + d[i][1];
      if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && !vis[nx][ny]){
        if(dp[x][y] + 1 <= dp[nx][ny]){
          dp[nx][ny] = min(dp[nx][ny],dp[x][y] + 1);
          vis[nx][ny] = true;
          que.push({nx,ny});
        }
      }
    }
  }
  return dp[ed.first][ed.second] >= INF ? -1 : dp[ed.first][ed.second];
}
signed main() {
  IO;
  while (cin >> n >> m >> q) {
    rep(i, 1, n) {
      rep(j, 1, m) {
        cin >> a[i][j];
        if (a[i][j] == 'S') star = {i, j};
        if (a[i][j] == 'T') ed = {i, j};
      }
    }
    memo.clear();
    rep(i, 1, q) {
      int rx, ry, tx, ty;
      cin >> rx >> ry >> tx >> ty;
      rx++, ry++, tx++, ty++;//输入的数据是从0开始的要改一下;
      memo[{rx, ry}].push_back({tx, ty});
    }
    int ans = bfs();
    cout << ans << '\n';
  }
  return 0;
}