看题解区的dalao是一个比一个牛逼，基本都写的BFS，有的甚至把图论、贪心、dp啥的都搬出来了，看不懂一点……

代码：

#include<iostream>
#define INF 0x3f3f3f3f//极大
using namespace std;

int a[1005][1005];//所有位置的颜色
bool vis[1005][1005];//标记某一位置是否被访问过
int dis[1005][1005];//dis[i][j]表示当前找到的从(1,1)走到(i,j)的最小代价
int m,n;

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

void dfs(int x,int y,int cost,int color){
	if(cost > dis[m][m])return ;//最优性剪枝，若当前方案的代价已经大于当前最优解，果断回溯
	if(x == m && y == m){//走到终点
		dis[x][y] = min(dis[x][y] ,cost);//记录最优解
		return ;
	}
	for(int i = 0;i < 4;i ++){//枚举四个方向
		int nx = dx[i] + x;
		int ny = dy[i] + y;
		if(vis[nx][ny] || nx < 1 || nx > m || ny < 1 || ny > m){//下一步的位置不合法
			continue;
		}
		if(a[nx][ny] || color){//当前位置和下一步位置中有一方颜色时
			if(! a[nx][ny]){
				if(cost + 2 > dis[nx][ny]){//依然是最优性剪枝
					continue;
				}
				dis[nx][ny] = cost +2;//记录当前最优解
				vis[nx][ny] = true;
				dfs(nx,ny,cost + 2,color);//递归
				vis[nx][ny] = false;
			}else if(a[nx][ny] == color && cost < dis[nx][ny]){//还是最优性剪枝
				vis[nx][ny] = true;
				dis[nx][ny] = cost;
				dfs(nx,ny,cost,color);
				vis[nx][ny] = false;
			}else if(a[nx][ny] != color && cost + 1 < dis[nx][ny]){//最优性剪枝
				dis[nx][ny] = cost + 1;
				vis[nx][ny] = true;
				dfs(nx,ny,cost + 1,a[nx][ny]);
				vis[nx][ny] = false;
			}
		}
	}
}

int main(){
	for(int i = 0;i < 1005;i ++)
		for(int j = 0;j < 1005;j ++)
			dis[i][j] = INF;//将dis数组全部赋值为极大值，便于统计最小代价
	cin>>m>>n;
	for(int i = 1;i <= n;i ++){
		int x,y,color;
		cin>>x>>y>>color;
		color ++;//数组初始都为0，因此用0表示没有颜色不合适，故将所有颜色对应的整数值都加上1
		a[x][y] = color;
	}
	vis[1][1] = true;
	dfs(1,1,0,a[1][1]);//调用
	if(dis[m][m] == INF)cout<<-1;//dis数组中对应值没有更新，即无解
	else cout<<dis[m][m];//有解
    return 0;
}

样例2过不了，输出为10