思路

没啥思考过程，照着题目跑bfs就过了。
大概就是跑的时候记格子的花费和是否用过魔法。
记录颜色时+1是因为比较方便区分白色。剪枝直接把同一格子花费大的剪掉就行了。
正确性的大概考虑：若经过同一格子两次，用魔法的状态肯定是一样的，并且金币只会递增。（不知所云）

代码

#include<bits/stdc++.h>
#define debug(x) cout<<"x="<<x<<endl
#define int long long
using namespace std;
const int maxn=1e5+7;
const int mod=1e9+7;
typedef long long ll;

//ifstream mycin("in.txt");
//ofstream mycout("out.txt");

int xx[]={0,0,1,-1},yy[]={1,-1,0,0};

inline void read(int &data){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    data=x*f;
}

struct node{
    int x,y,cost,used;
}; 

int m,n,cst[105][105],mp[105][105],used[105][105];
queue<node>q;

void bfs(){
    q.push((node){1,1,0,0});
    while(!q.empty()){
        node fro=q.front();
        q.pop();
        if(fro.x<1||fro.y<1||fro.x>m||fro.y>m) continue;
        if(fro.cost>=cst[fro.x][fro.y]) continue;
        cst[fro.x][fro.y]=fro.cost; //记录最小的花费 
        for(int d=0;d<4;d++){
            int dx=fro.x+xx[d],dy=fro.y+yy[d];
            if(mp[fro.x][fro.y]==mp[dx][dy]&&mp[dx][dy]) q.push((node){dx,dy,fro.cost,0});
            //有颜色且颜色相同 
            if(fro.used==mp[dx][dy]&&mp[dx][dy]) q.push((node){dx,dy,fro.cost,0});
            if(mp[fro.x][fro.y]!=mp[dx][dy]){
                if(mp[dx][dy]==0&&!fro.used){ //走去白色格子
                    q.push((node){dx,dy,fro.cost+2,mp[fro.x][fro.y]}); //下一个格子没有魔法 
                }else{ //红走黄、黄走红
                    q.push((node){dx,dy,fro.cost+1,0}); 
                }
            }
        }
    }
}

signed main(){
    int x,y,c;
    read(m);read(n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            cst[i][j]=0x3f3f3f3f; //最小需要的花费
            mp[i][j]=0;//无颜色 
        }
    }
    for(int i=1;i<=n;i++){
        read(x);read(y);read(c);
        mp[x][y]=c+1; //地图 
    }
    bfs();
    /*
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            cout<<cst[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    if(cst[m][m]==0x3f3f3f3f) cout<<-1<<endl;
    else cout<<cst[m][m]<<endl;
    return 0;
}