题解 | #对称飞行器#

从一个节点出发，搜索最短路径，选择广度优先搜索，核心在维护一个移动步数（深度）不减的队列；过程中每个节点只会入队列一次，入队列后将其标记，避免重复无效的入队操作。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;  // n行m列
    int s_x, s_y, e_x, e_y;
    vector<vector<int>> maze(n, vector<int> (m, 0));
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        for (int j = 0; j < m; ++j) {
            if (str[j] == '#') maze[i][j] = -1;
            if (str[j] == 'S') {s_x = i; s_y = j;}
            if (str[j] == 'E') {e_x = i; e_y = j;}
        }
    }
    queue<vector<int>> myQue; // 广度优先搜索所需队列
    myQue.push({s_x, s_y, 0, 5});
    maze[s_x][s_y] = -1;   // 每个元素只能压入队列一次
    while (!myQue.empty()) {
        vector<int> t = myQue.front();
        myQue.pop();
        int x = t[0], y = t[1], step = t[2], fly_count = t[3];
        if (x == e_x && y == e_y){
            cout << step <<endl;
            return 0;
        }
        if (x - 1 >= 0 && maze[x - 1][y] == 0) {
            myQue.push({x - 1, y, step + 1, fly_count});
            maze[x - 1][y] = -1;
        }
        if (x + 1 < n && maze[x + 1][y] == 0) {
            myQue.push({x + 1, y, step + 1, fly_count});
            maze[x + 1][y] = -1;
        }
        if (y - 1 >= 0 && maze[x][y - 1] == 0) {
            myQue.push({x, y - 1, step + 1, fly_count});
            maze[x][y - 1] = -1;
        }
        if (y + 1 < m && maze[x][y + 1] == 0) {
            myQue.push({x, y + 1, step + 1, fly_count});
            maze[x][y + 1] = -1;
        }
        if (maze[n - 1 - x][m - 1 - y] == 0 && fly_count) {
            myQue.push({n - 1 - x, m - 1 - y, step + 1, fly_count - 1});
            maze[n - 1 - x][m - 1 - y] = -1;
        }
    }
    cout << -1 <<endl;
    return 0;
}