60分求条

#include<bits/stdc++.h>
using namespace std;
int m,n,minn=2e9,u,v,w,vis[200][200],cd;//cd表示是否能使用魔法 
int nx[4]={0,0,1,-1},ny[4]={1,-1,0,0};//走向 
struct node{//1白 2红 3黄 
	int colour1;//原色
	int colour2;//用魔法改变的颜色 
}a[200][200];
void dfs(int x,int y,int corn){//corn是花费金币数
	if(x==m&&y==m){
		if(corn<minn){
			minn=corn;
		}
	} else{
		for(int i=0;i<4;i++){
			int bx=x+nx[i];
			int by=y+ny[i];
			if(bx>=1&&bx<=m&&by>=1&&by<=m&&vis[bx][by]==0){
				if(a[bx][by].colour1==a[x][y].colour1&&cd==0){
					vis[bx][by]=1;
					dfs(bx,by,corn);//费金币数不变 
					vis[bx][by]=0;//回溯 
				} else if(a[bx][by].colour1==a[x][y].colour2&&cd==1){//cd==1说明上一次使用魔法，所以比较colour2 
					vis[bx][by]=1;
					cd=0;//又可以使用魔法 
					dfs(bx,by,corn);
					cd=1;
					vis[bx][by]=0; 
				}else if(cd==0&&a[bx][by].colour1!=1){
					vis[bx][by]=1;
					dfs(bx,by,corn+1);//颜色不一样花费+1
					vis[bx][by]=0; 
				}else if(cd==1&&a[bx][by].colour1!=1){
					vis[bx][by]=1;
					cd=0;
					dfs(bx,by,corn+1);
					cd=1;
					vis[bx][by]=0;
				}else if(a[x][y].colour1!=1&&cd==0){//使用魔法 
					vis[bx][by]=1;
					cd=1;//魔法禁用
					a[bx][by].colour2=a[x][y].colour1;
					dfs(bx,by,corn+2);
					cd=0;
					vis[bx][by]=0; 
				}
			}
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j].colour1=1;//先默认为白色 
		}
	} 
	while(n--){
		cin>>u>>v>>w;
		a[u][v].colour1=w+2;
	}//赋值
	vis[1][1]=1;
	dfs(1,1,0); 
	if(minn==2e9) cout<<-1;
	else cout<<minn;
}