解题思路：

暴力出奇迹！数据范围不大，跟着题意直接爆搜加剪枝即可。

对于这种求最小值的爆搜，一个非常玄学且有效的剪枝就是记录每个格子当前所用的最短时间。

然后就没了。要注意把第一个点初始化好当初 dict 第一个点没初始化调了我半天。

CODE：

#include<iostream>
using namespace std;
int m, n, x, y, c, ans = 1e9, dict[101][101], num[101][101];
int xy[4][2]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool vis[101][101];
void dfs(int x, int y, int now, int lst)
{
    if (now > ans) return;
    if (x == m && y == m)
    {
        ans = min(ans, now);
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int dx = x + xy[i][0], dy = y + xy[i][1];
        if (dx >= 1 && dx <= m && dy >= 1 && dy <= m && vis[dx][dy] == 0 && (num[x][y] != -1 || num[dx][dy] != -1))
        {
            if (num[dx][dy] == -1) 
            {
                if (now + 2 < dict[dx][dy])
                {
                    vis[dx][dy] = 1;
                    dict[dx][dy] = now + 2;
                    dfs(dx, dy, now + 2, lst);
                    vis[dx][dy] = 0;
                }
            }
            else
            {
                if (num[dx][dy] == lst)
                {
                    if (now < dict[dx][dy])
                    {
                        vis[dx][dy] = 1;
                        dict[dx][dy] = now;
                        dfs(dx, dy, now, lst);
                        vis[dx][dy] = 0;
                    }
                }
                else
                {
                    if (now + 1 < dict[dx][dy])
                    {
                        vis[dx][dy] = 1;
                        dict[dx][dy] = now + 1;
                        dfs(dx, dy, now + 1, num[dx][dy]);
                        vis[dx][dy] = 0;
                    }
                }
            }
        }
    }
}
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            num[i][j] = -1;
            dict[i][j] = 1e9;
        }
    }
    while (n--)
    {
        cin >> x >> y >> c;
        num[x][y] = c;
    }
    vis[1][1] = 1;
    dict[1][1] = 0;
    dfs(1, 1, 0, num[1][1]);
    if (ans == 1e9) cout << -1;
    else cout << ans;
    return 0;
}