maze

maze

题目分析:

BFS进行状态转移，多次进入队列优化答案

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 310;

int t;
int n,m,k;
char g[N][N];
int d[N][N];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
vector<pii> mp[N][N];
int xa,ya,xb,yb;

void init(){
    mm(g,0);mm(d,0);mm(mp,0);
}

int bfs(){
    queue<pii> q;mm(d,inf);
    d[xa][ya] = 0;q.push({xa,ya});
    while(q.size()){
        pii t = q.front();
        q.pop();
        int x = t.first,y = t.second;
        for(int i = 0; i < 4; i ++ ){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a > n - 1 || b < 0 || b > m - 1) continue;
            if(g[a][b] == '#') continue;
            if(d[a][b] > d[x][y] + 1){
                d[a][b] = d[x][y] + 1;
                q.push(mk(a,b));
            }
        }
        for(int i = 0; i < mp[x][y].size(); i ++ ){
            int a = mp[x][y][i].first;
            int b = mp[x][y][i].second;
            if(a < 0 || a > n - 1 || b < 0 || b > m - 1) continue;
            if(g[a][b] == '#') continue;
            if(d[a][b] > d[x][y] + 3){
                d[a][b] = d[x][y] + 3;
                q.push(mk(a,b));
            }
        }
    }
    return d[xb][yb];
}
int main() {
    while(cin >> n >> m >> k){
        init();
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < m; j ++ ){
                cin >> g[i][j];
                if(g[i][j] == 'S'){
                    xa = i,ya = j;
                }
                if(g[i][j] == 'T'){
                    xb = i,yb = j;
                }
            }
        }
        while(k -- ){
            int a,b,c,d;
            cin >> a >> b >> c >> d;
            mp[a][b].push_back(mk(c,d));
        }
        int t = bfs();
        if(t == inf) cout<<-1<<endl;
        else cout<<t<<endl;        
    }    
    return 0;
}