#include<iostream>
#include<cstdio>
using namespace std;
int q[110][110]/*格子颜色*/,d[110][110]/*到达每个格子所花的最少金币*/,xx[4]={1,-1,0,0},yy[4]={0,0,1,-1}/*坐标变化*/;
bool z[110][110];//是否走过 
int m,n,x,y,c,s;
void xz(int a,int b,int s,int o)//a,b是坐标,s是金币,o是颜色 
{
    if(a==m&&b==m)
	{
		d[m][m]=min(s,d[m][m]);
		return ;
	} 
    for(int i=0;i<4;i++)
    {
    	int x1=a+xx[i],y1=b+yy[i];
    	if((x1!=0)&&(x1<=n)&&(y1!=0)&&(y1<=n)/*判断边界*/&&(!z[x1][y1])/*判断是否走过*/&&((q[x1][y1])||(q[a][b])))//两个格子中至少一个有颜色 
    	{
    		if(q[x1][y1]==0&&s+2<d[x1][y1])//将要走的格子是无色 +所用金币少于原金币 
    		{
    			d[x1][y1]=s+2;//更新 
    			z[x1][y1]=1;
    			xz(x1,y1,s+2,o);//使用魔法 
    			z[x1][y1]=0;
			}
    		if(o==q[x1][y1]&&s<d[x1][y1])//颜色一样的情况+所用金币少于原金币 
    		{
    			d[x1][y1]=s;//更新 
    			z[x1][y1]=1;
    			xz(x1,y1,s,o);//不用花费金币 
    			z[x1][y1]=0;
			}
			if(q[a][b]!=q[x1][y1]&&s+1<d[x1][y1])//颜色不一样 +所用金币少于原金币
    		{
    			d[x1][y1]=s+1;//更新 
    			z[x1][y1]=1;
    			xz(x1,y1,s+1,d[x1][y1]);//花费一个金币 
    			z[x1][y1]=0;
			}
		}
	}
}    
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
	        d[i][j]=99999999;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y>>c;
		q[x][y]=c+1;
	}
	z[1][1]=1;
	xz(1,1,0,q[1][1]);
	if(d[m][m]<99999999)cout<<d[m][m]<<endl;
	else cout<<-1<<endl;
	return 0;
}

样例1总是输出6

参考了题解，用的DFS加剪枝