题解 | ACM中的AC题

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int Min(int a, int b) {
    if(a < 0) {
        return b;
    }
    if(b < 0) {
        return a;
    }
    return min(a,b);
}
struct Pt {
    int y;
    int x;
};
int main() {
    int n, m, y, x;
    cin >> n >> m >> y >> x;
    x--;
    y--;
    vector<string> map(n);
    for(auto& v : map) {
        cin >> v;
    }
    vector<pair<int,int>> round = {
        {0,1},{0,-1},{1,0},{-1,0}
    };
  	// 双人步数
    vector<vector<int>> step(n, vector<int>(m,-1));
  	// 单人步数
    vector<vector<int>> step2(n, vector<int>(m,-1));
    deque<pair<Pt,Pt>> dq;
    deque<Pt> dq2;
    dq.emplace_back(Pt{y,x},Pt{y,x});
    step[y][x] = 0;
    while(dq.size()) {
        auto pt = dq.front();
        dq.pop_front();
        auto cStep = step[pt.first.y][pt.first.x];
        for(auto& off : round) {
            auto my = pt.first.y + off.first;
            auto mx = pt.first.x + off.second;
            auto ny = pt.second.y - off.first;
            auto nx = pt.second.x - off.second;
            if( mx < 0 || mx >= m || my < 0 || my >= n) {
                continue;
            }
            if( nx < 0 || nx >= m || ny < 0 || ny >= n) {
                continue;
            }
            if(map[my][mx] == '#' || map[ny][nx] == '#') {
                continue;
            }
            if(step[my][mx] != -1) {
                continue;
            }
            auto ok = false;
            if(map[my][mx] == '@') {
                step2[ny][nx] = Min(cStep + 1, step2[ny][nx]);
                dq2.emplace_back(Pt{ny,nx});
                ok = true;
            }
            if(map[ny][nx] == '@') {
                step2[my][mx] = Min(cStep + 1, step2[my][mx]);
                dq2.emplace_back(Pt{my,mx});
                ok = true;
            }
            // 可到达点不计入
            if(ok) {
                continue;
            }
            step[my][mx] = cStep + 1;
            dq.emplace_back(Pt{my,mx},Pt{ny,nx});
        }
    }
    // 没有找到传送点则无法逃脱
    if(dq2.size() == 0) {
        cout << -1 << endl;
        return 0;
    }
  	// 记录当前最小步数
    int curStep = -1;
    while(dq2.size()) {
        auto pt = dq2.front();
        dq2.pop_front();
        auto ptStep = step2[pt.y][pt.x];
        if( curStep == -1) {
            curStep = ptStep;
        } else {
		  	// 当前步数过大则移动到最后 保证最小步数优先计算
            if(ptStep > curStep + 1) {
                dq2.emplace_back(pt);
                continue;
            } else {
                curStep = ptStep;
            }
        }
        if(map[pt.y][pt.x] == '@') {
		  	// 第一个达成的就是最优解
            cout << curStep << endl;
            return 0;
        }
        for(auto& off : round) {
            auto my = pt.y + off.first;
            auto mx = pt.x + off.second;
            if( mx < 0 || mx >= m || my < 0 || my >= n) {
                continue;
            }
            if(map[my][mx] == '#') {
                continue;
            }
            if(step2[my][mx] > 0 && step2[my][mx] <= ptStep + 1) {
                continue;
            }
            step2[my][mx] = ptStep + 1;
            dq2.emplace_back(Pt{my,mx});
        }
    }
}
// 64 位输出请用 printf("%lld")