悬赏关注

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;

typedef long long l;
l m, n, a[105][105], ans = 2e9, val[105][105], ax[] = {0, 1, -1, 0, 0}, ay[] = {0, 0, 0, 1, -1};

struct Grid {
    l x, y, money;
    bool v;
};

void bfs() {
    queue<Grid> q;
    q.push({1, 1, 0, 0});
    while (!q.empty()) {
        Grid g = q.front();
        q.pop();
        if (g.money >= ans) continue;
        if (g.x == m && g.y == m) {
            ans = min(ans, g.money);
            continue;
        }
        for (l i = 1; i <= 4; ++i) {
            Grid g2 = {g.x + ax[i], g.y + ay[i], g.money, 0};
            if (g2.x > 0 && g2.y > 0 && g2.x <= m && g2.y <= m) {
                if (a[g2.x][g2.y] != 0) {
                    if (a[g2.x][g2.y] != a[g.x][g.y]) g2.money++;
                    if (g2.money > val[g2.x][g2.y]) {
                        q.push(g2);
                        val[g2.x][g2.y] = g2.money;
                    }
                }
                if (a[g2.x][g2.y] == 0 && g.v == 0) {
                    g2.v = 1;
                    a[g2.x][g2.y] = a[g.x][g.y];
                    if (g2.money > val[g2.x][g2.y]) {
                        q.push(g2);
                        val[g2.x][g2.y] = g2.money;
                    }
                }
            }
        }
        if (g.v == 1) a[g.x][g.y] = 0;
    }
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (l i = 1; i <= n; ++i) {
        l x, y;
        bool c;
        scanf("%lld%lld%d", &x, &y, &c);
        a[x][y] = (c == 0)?2:1;
    }
    bfs();
    if (ans == 2e9) ans = -1;
    printf("%lld", ans);
    return 0;
}