题解

#include <bits/stdc++.h>
using namespace std;
//定义方向
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
struct State{
    int x, y;//当前位置坐标
    int cost;//已花费的金币
    int lastcolor;//上一个格子的颜色
    bool usedmagic;//是否刚刚使用了魔法
};
int main(){
    int m,n;
    cin>>m>>n;
    //初始化棋盘，-1表示无色，0表示红色，1表示黄色
    vector <vector <int> > qw(m + 1, vector<int>(m + 1, -1));
    //读取有颜色的格子
    for(int i = 0;i < n;i++){
        int x, y, c;
        cin>>x>>y>>c;
        qw[x][y] = c;
    }
    //检查起点和终点是否有颜色
    if(qw[1][1] == -1){
        cout<<-1;
        return 0;
    }
    //初始化最小花费数组，记录到达每个位置的最小花费
    vector<vector<vector<int>>> yu(m+1, vector<vector<int>>(m+1, vector<int>(2, INT_MAX)));
    queue<State> q;
    //初始状态：位于(1,1)，花费0金币，上一个颜色是起点的颜色，没有使用魔法
    q.push({1, 1, 0, qw[1][1], false});
    yu[1][1][0] = 0;
    int result = -1;
    while(!q.empty()){
        State current = q.front();
        q.pop();
        //如果到达终点，更新结果
        if(current.x == m and current.y == m){
            if(result == -1 or current.cost < result){
                result = current.cost;
            }
            continue;
        }
        if(current.cost > yu[current.x][current.y][current.usedmagic]){
            continue;
        }
        //尝试四个方向移动
        for(int i = 0; i < 4; i++) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            //检查新位置是否在棋盘内
            if(nx < 1 or nx > m or ny < 1 or ny > m){
            	continue;
			}
            //如果新位置有颜色
            if(qw[nx][ny] != -1){
                int newcost = current.cost;
                //如果颜色不同，花费1金币
                if(qw[nx][ny] != current.lastcolor){
                    newcost += 1;
                }
                //如果花费更少，更新状态
                if(newcost < yu[nx][ny][0]){
                    yu[nx][ny][0] = newcost;
                    q.push({nx, ny, newcost, qw[nx][ny], false});
                }
            }
            //如果新位置没有颜色，且上次没有使用魔法
            else if(!current.usedmagic){
                //花费2金币使用魔法，将格子变为与当前格子相同的颜色
                int wer = current.cost + 2;
                //如果花费更少，更新状态
                if(wer < yu[nx][ny][1]){
                    yu[nx][ny][1] = wer;
                    q.push({nx, ny, wer, current.lastcolor, true});
                }
            }
        }
    }
    cout<<result;
    return 0;
}