```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[101][101],flag[101][101],f[101][101];
//a[i][j]颜色flag[i][j]本色还是变色f[x][y]记忆数组
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int x,y,w;
void fan(int x,int y)//递归推下一个格子代价
{
int i,j;
//失败出口
if(x<1||x>m||y<1||y>m)//下标越界
return ;
if(a[x][y]==-1)//当前无色
return ;
//成功
if(x==m&&y==m)
return ;
//递归四个方向
for(i=1;i<=4;i++)
{
//四种情况
if(a[x][y]==a[x+dx[i]][y+dy[i]])
{
//同色，判断走不走，下一个代价是否变小
if(f[x][y]<f[x+dx[i]][y+dy[i]])
{
f[x+dx[i]][y+dy[i]]=f[x][y];//同色不花钱
fan(x+dx[i],y+dy[i]);
}
}
//剩下的肯定不同色
else if(a[x+dx[i]][y+dy[i]]!=-1)
{
//如果一定不是无色(异色)
//判断走不走
if(f[x][y]+1<f[x+dx[i]][y+dy[i]])
{
f[x+dx[i]][y+dy[i]]=f[x][y]+1;
fan(x+dx[i],y+dy[i]);
}
}
//剩下的肯定无色
else if(flag[x][y]==1&&a[x+dx[i]][y+dy[i]]==-1)//保证一定不会用两次魔法（只有变与无一种情况会用两次魔法）
{
//当前变色来的，跳过
continue;
}
//要变色了
else
{
//当前本色来的，判断走不走
if(f[x][y]+2<f[x+dx[i]][y+dy[i]])
{
f[x+dx[i]][y+dy[i]]=f[x][y]+2;
a[x+dx[i]][y+dy[i]]=a[x][y];//变色
flag[x+dx[i]][y+dy[i]]=1;
fan(x+dx[i],y+dy[i]);
//回溯后恢复标记
a[x+dx[i]][y+dy[i]]=-1;
flag[x+dx[i]][y+dy[i]]=0;
}
}
}
}
int main()
{
int i,j;
cin>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
a[i][j]=-1;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
f[i][j]=999999;
f[1][1]=0;//注意边界，走到1，1不要代价
for(i=1;i<=n;i++)
{
cin>>x>>y>>w;
a[x][y]=w;
}
fan(1,1);
if(f[m][m]==999999)
{
cout<<-1;
return 0;
}
cout<<f[m][m];
return 0;
}
```
呐
都给你注释好了
AC代码，自己看吧
by 决心少年 @ 2019-11-13 22:10:31
~~我是蒟蒻，不是蒻蒟，别来找我~~
by blackfrog @ 2019-11-13 22:11:08
@[Alpha_Fuze](/user/160352)
看到了吗qwq
by 决心少年 @ 2019-11-13 22:13:30
@[血祭少年](/user/215603) 蟹蟹！
by Alpha_Fuze @ 2019-11-13 22:14:53
@[Alpha_Fuze](/user/160352)
不客气qwq
by 决心少年 @ 2019-11-13 22:15:30