大致思路： 深搜+剪枝，下格无色那里用了贪心
望有大佬能解 加关注

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC optimize(2)
using namespace std;

const int MAX = 0x3f3f3f3f;
const int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};

int m, n, ans = MAX; bool vis[105][105];
int Map[105][105]/*地图*/, f[105][105]/*剪枝用数组*/;

void dfs(int x, int y, int cnt/*金币计数*/, bool mg/*能否使用魔法*/);

int main(){
	int x, y, color, i, j; scanf("%d %d", &m, &n);
	for(i = 1;i <= n;i ++){
		scanf("%d %d %d", &x, &y, &color);
		Map[x][y] = color + 1; //注:1:红色 2:黄色 
	}
	
	memset(f, MAX, sizeof(f));
	vis[1][1] = 1; dfs(1, 1, 0, 1);
	
	if(ans == MAX) printf("-1");
	else printf("%d", ans);
	
	return 0;
}

void dfs(int x, int y, int cnt, bool mg){
	if(cnt >= ans || cnt >= f[x][y]) return; //剪枝 
	f[x][y] = cnt;
	//到达终点 
	if(x == m && y == m){ans = min(ans, cnt); return;} 
	//继续搜索 
	else{
		int i;
		for(i = 0;i < 4;i ++){
			int nx = x + dir[i][0]; int ny = y + dir[i][1];
			if(nx < 1 || nx > m || ny < 1 || ny > m || vis[nx][ny]) continue;
			vis[nx][ny] = 1;
			//下格无色
			if(!Map[nx][ny]) 
				/*可用*/if(mg){Map[nx][ny] = Map[x][y]; dfs(nx, ny, cnt + 2, 0); Map[nx][ny] = 0;} 
				/*不可用*/else return;
			//下格有色 
			else 
				/*同色*/if(Map[x][y] == Map[nx][ny]) dfs(nx, ny, cnt, 1);
				/*异色*/else dfs(nx, ny, cnt + 1, 1);
			//回溯
			vis[nx][ny] = 0; 
		}
	}
}