调了一天找不到代码错在哪里，于是开始考虑思路是否有误:(

思路如下：在 BFS 队列节点中存储当前位置和上一步的位置（第一次都设为 $(1,1)$），接下来遍历四个方向，进行搜索：

1. 如果当前位置和目标位置都有颜色，依照题意计算代价
2. 如果当前位置和目标位置都没有颜色，则无法通行
3. 如果当前位置有颜色，目标位置无颜色，贪心的将目标位置的颜色变为当前位置的颜色
4. 如果当前位置无颜色，目标位置有颜色，考虑上一步所在位置的颜色计算代价

并且容易发现，只有被更新的位置才可能更新其他的位置，所以如果目标位置成功被更新，则将目前位置作为节点中的“上一步位置”，目标位置作为节点中的“当前位置”，放入队列中进行搜索

以下是代码：

#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(){
	freopen("P3956_7.in","r",stdin);
	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];	//如果无法更新目标位置，说明目标位置无法到达，输出-1
	return 0;
}