想法大概是DFS，用一个变量ma表示能否使用魔法（毕竟不能使用魔法时意味着临走前要恢复） 不确定哪里有问题，希望有大佬能帮忙看一看，衷心感谢

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define MAXN 0x7fffffff
using namespace std;
int m,n;
int a[1100][1100];//颜色
int bl[1100][1100];//是否走过
int ans,minum=MAXN;
int i,j,p,q,w;
int f[4][2] = {1,0, 0,1, -1,0, 0,-1};
int d[1100][1100];//各个格子的最小花费
//set<xy> mo;
//0：无色
void search(int x,int y,int c,int ma){
	//参数分别是：x,y,上一轮总花费，能否使用魔法
	//printf("%d %d %d %d %d\n",x,y,c,m,minum);
	if((x==m)&&(y==m)){
		minum=min(c,minum);
		return;
	}
	int p,q;
	for(int i = 0;i<4;i++){
		p = x+f[i][0];
		q = y+f[i][1];
		int now = a[x][y];
		if(!ma)a[x][y] = 0;//不能用魔法代表这一轮离开前要恢复当前的格子
		if(p<1||q<1||p>m||q>m)continue;
		if(!bl[p][q]){
			//没走过
			if(a[p][q]==0){
				if(ma&&d[p][q]>c+2){
					//目前所处的格子本来就有颜色
					bl[p][q] = 1;
					d[p][q]=c+2;
					a[p][q]=now;//使用魔法
					search(p,q,c+2,0);
					bl[p][q]=0;
				}
			}
			else if(a[p][q]==now&&d[p][q]>c){
				bl[p][q] = 1;
				d[p][q]  =c;
				search(p,q,c,1);
				bl[p][q] = 0;
			}
			else if(d[p][q]>c+1){
				bl[p][q] = 1;
				d[p][q] = c+1;
				search(p,q,c+1,1);
				bl[p][q] = 0;
			}
		}
		
			
		}
		
		
}

int main(){
	scanf("%d%d",&m,&n);
	
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++) d[i][j]=MAXN;
	
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&q,&p,&w);
		a[q][p]=w+1;
	}
	bl[1][1]=1;
	search(1,1,0,1);
	if(minum==MAXN){
		printf("-1");
		return 0;
	}
	printf("%d",minum);
	return 0;
}