dfs解法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;
int mp[N][N];
int m, n;
int dist[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


void dfs(int x, int y, int pay, bool magic){
    if(dist[x][y] <= pay) return;
    dist[x][y] = pay;
    if(x == m && y == m)return;

    for (int i = 0; i < 4; i ++ ){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx > m || xx < 1 || yy > m || yy < 1)continue;
        if(mp[xx][yy] == mp[x][y])dfs(xx, yy, pay, false);
        else if(mp[xx][yy] != -1 )dfs(xx, yy, pay+1, false);
        else if(!magic && mp[xx][yy] == -1){
            mp[xx][yy] = mp[x][y];
            dfs(xx, yy, pay+2, true);
            mp[xx][yy] = -1;
        }
    }

}

int main(){
    memset(mp, -1, sizeof mp);
    memset(dist, 0x3f, sizeof dist);
    cin >> m >> n;
    int x, y, c;
    for (int i = 1; i <= n; i ++ ){
        cin >> x >> y >> c;
        mp[x][y] = c;
    }

    dfs(1, 1, 0, false);

    if(dist[m][m] == 0x3f3f3f3f)cout << -1;
    else cout << dist[m][m];

    return 0;
}