原題鏈接

思路：找出最短路徑，然后判斷是否存在連續三個點是橫縱坐標相等的，如果有就步數減1

但是有兩個樣例過不了

錯誤原因：在錯誤的測試案例中，最短路徑可能有多條，而我剛好選了一條比較曲折的，不能一下子走兩步

#include <bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> arr(n + 2, vector<int>(m + 2, -1));vector<vector<int>> state(n + 2, vector<int>(m + 2, 0));vector<vector<pair<int, int>>> lastNode(n + 2, vector<pair<int, int>>(m + 2, {0, 0}));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {int num;cin >> num;arr[i][j] = num;}}int step = 0;queue<pair<int, int>> p, c;bool isFind = false;p.emplace(1, 1);while (!p.empty()) {while (!p.empty()) {auto cur = p.front();if (cur.first == n && cur.second == m) {isFind = true;break;}p.pop();if (arr[cur.first - 1][cur.second] == 0 && state[cur.first - 1][cur.second] == 0) {c.emplace(cur.first - 1, cur.second);state[cur.first - 1][cur.second] = 1;lastNode[cur.first - 1][cur.second] = {cur.first, cur.second};}if (arr[cur.first + 1][cur.second] == 0 && state[cur.first + 1][cur.second] == 0) {c.emplace(cur.first + 1, cur.second);state[cur.first + 1][cur.second] = 1;lastNode[cur.first + 1][cur.second] = {cur.first, cur.second};}if (arr[cur.first][cur.second - 1] == 0 && state[cur.first][cur.second - 1] == 0) {c.emplace(cur.first, cur.second - 1);state[cur.first][cur.second - 1] = 1;lastNode[cur.first][cur.second - 1] = {cur.first, cur.second};}if (arr[cur.first][cur.second + 1] == 0 && state[cur.first][cur.second + 1] == 0) {c.emplace(cur.first, cur.second + 1);state[cur.first][cur.second + 1] = 1;lastNode[cur.first][cur.second + 1] = {cur.first, cur.second};}}if (isFind) break;step++;p = c;while (!c.empty()) c.pop();}vector<pair<int, int>> result;if (!isFind) {cout << -1 << endl;return 0;} else {int i = n, j = m;while (i != 1 || j != 1) {result.emplace_back(i, j);auto post = lastNode[i][j];i = post.first;j = post.second;}}
//    cout << "1 1" << endl;
//    for (int i = result.size() - 1; i >= 0; --i) {
//        auto cur = result[i];
//        cout << cur.first << " " << cur.second << endl;
//    }result.emplace_back(1, 1);int count = result.size() - 1; // 經過多少個點，減去1 就是單步走的最短路徑for (int i = result.size() - 1; i >= 2; --i) {if (result[i].first == result[i - 1].first && result[i].first == result[i - 2].first) {count--;i = i - 1; // 循環結束會減一 所以這里只要減1 一共減2} else if (result[i].second == result[i - 1].second && result[i].second == result[i - 2].second) {count--;i = i - 1;}}cout << count << endl;return 0;
}