思路:

简单bfs即可,只不过细节挺多

Code:

#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
const int N=110,INF=0x3f3f3f3f;
int n,m,color[N][N],b[N][N],dist[N][N][2];
struct Q{
    int x,y,state; //state为0表示当前来到(x,y)没有使用魔法
};
int get(int x_1,int y_1,int x_2,int y_2){
    return (b[x_1][y_1]==b[x_2][y_2]?0:1);
}
int bfs(){
    queue<Q>q;
    q.push({1,1,0});
    memset(dist,0x3f,sizeof dist);
    dist[1][1][0]=0;
    while(!q.empty()){
        Q t=q.front();
        q.pop();
        //cout<<t.x<<" "<<t.y<<" "<<t.state<<" "<<dist[t.x][t.y][t.state]<<endl;
        for(int i=0;i<4;i++){
            int xx=t.x+dx[i];
            int yy=t.y+dy[i];
            if(xx<1||xx>n||yy<1||yy>n||color[xx][yy]==-1) continue;
            int cost=get(xx,yy,t.x,t.y);
            if(dist[xx][yy][0]>dist[t.x][t.y][t.state]+cost){
                dist[xx][yy][0]=dist[t.x][t.y][t.state]+cost;
                q.push({xx,yy,0});
            }
        }
        if(t.state) continue;
        for(int i=0;i<4;i++){
            int xx=t.x+dx[i];
            int yy=t.y+dy[i];
            if(xx<1||xx>n||yy<1||yy>n||color[xx][yy]!=-1) continue;
            if(dist[xx][yy][1]>dist[t.x][t.y][0]+2){
                dist[xx][yy][1]=dist[t.x][t.y][0]+2;
                b[xx][yy]=color[t.x][t.y];
                q.push({xx,yy,1});
            }
        }
    }
    int res=min(dist[n][n][0],dist[n][n][1]);
    return (res==INF?-1:res);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            color[i][j]=-1;
            b[i][j]=-1;
        }
    }
    while(m--){
        int x,y,c;
        cin>>x>>y>>c;
        color[x][y]=c;
        b[x][y]=c;
    }
    cout<<bfs()<<endl;
    return 0;
}