贴个F的代码

先考虑单纯的最短路，然后考虑限制一个方向且最多可到达一个障碍，求最小值。

#include <bits/stdc++.h>

int main(void) {
    int n, m;
    std::cin >> n >> m;
    bool grid[n][m];
    memset(grid, 0, sizeof(grid));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char ch;
            std::cin >> ch;
            grid[i][j] = (ch == '.');
        }
    }
    constexpr int INF = 0x3f3f3f3f;
    constexpr int offset[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int ret1 = [&]() {
        int dis[n][m];
        memset(dis, 0x3f, sizeof(dis));
        using T = std::tuple<int, int, int>; // dis, x, y
        std::priority_queue<T, std::vector<T>, std::greater<>> heap;
        heap.emplace(0, 0, 0);
        while (!heap.empty()) {
            auto [d, x, y] = heap.top();
            heap.pop();
            if (dis[x][y] <= d) {
                continue;
            }
            if (x + 1 == n && y + 1 == m) {
                return d;
            }
            dis[x][y] = d;
            for (int i = 0; i < 4; ++i) {
                int xx = x + offset[i][0], yy = y + offset[i][1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && grid[xx][yy] && d + 1 < dis[xx][yy]) {
                    heap.emplace(d + 1, xx, yy);
                }
            }
        }
        return INF;
    }();
    int ret2 = [&]() {
        using ARRAY = std::array<int, 8>;
        int dis[n][m][4][2];
        memset(dis, 0x3f, sizeof(dis));
        using T = std::tuple<int, int, int, int, int>; // dis, x, y, disacrd, selected
        std::priority_queue<T, std::vector<T>, std::greater<>> heap;
        for (int i = 0; i < 4; ++i) {
            heap.emplace(0, 0, 0, i, 0);
        }
        while (!heap.empty()) {
            auto [d, x, y, pos, state] = heap.top();
            heap.pop();
            if (dis[x][y][pos][state] <= d || dis[x][y][pos][state] <= d) {
                continue;
            }
            if (x + 1 == n && y + 1 == m) {
                return d;
            }
            dis[x][y][pos][state] = d;
            for (int i = 0; i < 4; ++i) {
                if (i == pos) {
                    continue;
                }
                int xx = x + offset[i][0], yy = y + offset[i][1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
                    if (grid[xx][yy]) {
                        if (d + 1 < dis[xx][yy][pos][state]) {
                            heap.emplace(d + 1, xx, yy, pos, state);
                        }
                    } else {
                        if (state == 0 && d + 1 < dis[xx][yy][pos][1]) {
                            heap.emplace(d + 1, xx, yy, pos, 1);
                        }
                    }
                }
            }
        }
        return INF;
    }();
    int ret = std::min(ret1, ret2);
    if (ret == INF) {
        ret = -1;
    }
    std::cout << ret << std::endl;
    return 0;
}