这是一道明显的深搜题目，处理点细节：
- 这是个正方形的，边长为m，而不是边长为n,m的长方形
- 这道题把黄色红色设成1和0，不要把0来当作没有染色的格子
- 迈向一个新的格子有三种情况，格子颜色一样就继承花费，不一样就加一，新格子没颜色就刷上颜色然后加二（刷成同色会比异色更优吧，（不确定，但是能A））
AC代码：
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e3 + 3, M = 1e2 + 2, INF = 0x3f3f3f3f;
int m, n, min_ans = 1e9;
int mp[M][M], ans[M][M]; // ans剪枝，表示走到指定位置的最小价值
bool vis[M][M];
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
void dfs(int x, int y, int cost, bool isR) {// 退出条件和剪枝if (x < 1 || x > m || y < 1 || y > m || cost >= min_ans)return;if (cost >= ans[x][y])return;elseans[x][y] = cost;if (x == m && y == m) {min_ans = min(min_ans, cost);return;}for (int k = 0; k < 4; k++) {int n_x = x + dx[k], n_y = y + dy[k];if (n_x < 1 || n_x > m || n_y < 1 || n_y > m)continue;if (vis[n_x][n_y])continue;// 同色if (mp[n_x][n_y] == mp[x][y]) {vis[n_x][n_y] = true;dfs(n_x, n_y, cost, true);vis[n_x][n_y] = false;}// 异色else if (abs(mp[n_x][n_y] - mp[x][y]) == 1) {vis[n_x][n_y] = true;dfs(n_x, n_y, cost + 1, true);vis[n_x][n_y] = false;}// 变颜色else {if (!isR)continue;// 变成和现在一样的颜色，策略会更优mp[n_x][n_y] = mp[x][y];vis[n_x][n_y] = true;dfs(n_x, n_y, cost + 2, false);vis[n_x][n_y] = false;mp[n_x][n_y] = INF;}}
}
int main(int argc, char *argv[]) {cin >> m >> n;memset(mp, 0x3f, sizeof(mp));memset(ans, 0x3f, sizeof(ans));for (int i = 1; i <= n; i++) {int x, y, c;cin >> x >> y >> c;mp[x][y] = c;}dfs(1, 1, 0, true);cout << (min_ans == 1e9 ? -1 : min_ans);return 0;
}