maze（bfs搜索）

题目：

一个n*m的迷宫。问从起点走到终点最短用时。往上下左右走1格花费1s。用一次传送门花费3s。

做法：

简单题。从起点开始bfs搜到达所有点的最短用时就好了。从每个点转移到上下左右位置以及该点可以开启的传送门的位置。题目不难，细节比较多一点。
可以看看我的写法，用优先队列优化bfs。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 310;
const int inf = 0x3f3f3f3f;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
char str[N][N];
int n, m, q;
struct node{
    int x, y, step;
    node(int x = 0, int y = 0, int s = 0):x(x),y(y),step(s){}
    bool operator < (const node& rh)const{
        return step > rh.step;
    }
}s, t;
vector <pair<int,int> > tp[N*N];
int tim[N][N];
int get(int x, int y){
    return (x-1)*m+y;
}
void bfs(void){
    memset(tim, inf, sizeof tim);
    priority_queue<node> q;
    s.step = 0;
    q.push(s);
    tim[s.x][s.y] = 0;
    while (!q.empty()){
        node u = q.top(); q.pop();
        if (tim[u.x][u.y] != u.step) continue;
        for (int i = 0; i < 4; ++i){
            int x = u.x+dx[i], y = u.y+dy[i];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (str[x][y] == '#') continue;
            if (tim[x][y] > u.step+1){
                tim[x][y] = u.step+1;
                q.push(node(x, y, u.step+1));
            }
        }
        int h = get(u.x, u.y);
        for (int i = 0; i < tp[h].size(); ++i){
            int x = tp[h][i].first, y = tp[h][i].second;
            if (str[x][y] == '#') continue;
            if (tim[x][y] > u.step+3){
                tim[x][y] = u.step+3;
                q.push(node(x, y, u.step+3));
            }
        }
    }
}
int main(void){ 
    IOS;
    while (cin >> n >> m >> q){
        for (int i = 1; i <= n; ++i){
            cin >> (str[i]+1);
            for (int j = 1; j <= m; ++j){
                if (str[i][j] == 'S'){
                    s = node(i, j, 0);
                }else if (str[i][j] == 'T'){
                    t = node(i, j, 0);
                }
            }
        }
        for (int i = 1; i <= get(n, m); ++i) tp[i].clear();
        for (int i = 1; i <= q; ++i){
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            x1++, y1++, x2++, y2++;
            tp[get(x1, y1)].push_back(make_pair(x2, y2)); 
        }
        bfs();
        if (tim[t.x][t.y] == inf) cout << -1 << endl;
        else cout << tim[t.x][t.y] << endl;
    }
    return 0;
}