思路：BFS，根据题意判断每一步的代价

代码：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

int n,m,col[106][106],ans[105][105];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

struct NodeQ{
	int x,y,lx,ly;		//当前坐标，来时的坐标（用于判断当前坐标为无色格子时的代价）
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>m>>n;
	for(int i = 1;i <= n;i += 1)
	{
		int x,y,c;
		cin>>x>>y>>c;
		col[x][y] = c + 1;	//无色为0，有色为1,2
	}
	queue<NodeQ> que;
	memset(ans,-1,sizeof(ans));		//初始化-1
	ans[1][1] = 0;
	que.push(NodeQ{1,1,1,1});
	while(!que.empty())
	{
		int x = que.front().x,y = que.front().y,lx = que.front().lx,ly = que.front().ly;
		que.pop();
		for(int i = 0;i <= 3;i += 1)
		{
			int cx = x + dir[i][0],cy = y + dir[i][1];
			if(1 <= cx && cx <= m && 1 <= cy && cy <= m)
			{
                if(col[x][y] == 0 && col[cx][cy] == 0)		//无色格子不能相互同行
				{
					continue;
				}
				int delta;		//这一步所需的代价
				if(col[x][y] == col[cx][cy] || (col[x][y] == 0 && col[lx][ly] == col[cx][cy]))		//如果两个格子颜色相同或者当前格子无色且被转换成与目标格相同的颜色
				{
					delta = 0;
				}
				else if((col[x][y] != 0 && col[cx][cy] != 0) || (col[x][y] == 0 && col[lx][ly] != col[cx][cy]))	//两个格子颜色不同或者当前格子无色且被转换成与目标格不同的颜色
				{
					delta = 1;
				}
				else if(col[cx][cy] == 0)	//如果当前格子有色且目标格无色，贪心的将目标格转换成与当前格子相同的颜色
				{
					delta = 2;
				}
				if(ans[cx][cy] > ans[x][y] + delta || ans[cx][cy] == -1)	//如果目标格已知的代价大于新代价或目标格未被更新
				{
					ans[cx][cy] = ans[x][y] + delta;
					que.push(NodeQ{cx,cy,x,y});
				}
			}	
		}
	}
	cout<<ans[m][m];
	return 0;
}