万绿丛中一点红 95分 错了第10个点

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,a[101][101],mf[101][101],tu[101][101];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int check(int x,int y){
	int ans=0;
	for(int i=0;i<4;i++) if(a[x+dx[i]][y+dy[i]]) ans++;
	if(ans>1) return 1;return 0;
}
struct asd{
	int x,y,color,money;
};
asd cr(int a,int b,int c,int d){
	asd q;
	q.x=a;q.y=b;q.color=c;q.money=d;
	return q;
}
int main(){
//	freopen("chess.in","r",stdin);
//	freopen("chess.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z+1;
	}//cout<<endl;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			tu[i][j]=1e8;
			if(a[i][j]) mf[i][j]=1;
			else mf[i][j]=check(i,j);
			//cout<<a[i][j]<<" ";
		}//cout<<endl;
	}//cout<<endl;
	queue<asd>q;mf[m][m]=1;
	q.push(cr(1,1,a[1][1],0));tu[1][1]=0;
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,color1=q.front().color,money1=q.front().money;q.pop();
		for(int i=0;i<4;i++){
			int lx=x+dx[i],ly=y+dy[i],money=money1,color=color1;
			if(!mf[lx][ly]||lx<1||lx>m||ly<1||ly>m) continue;
			if(!a[lx][ly]) money+=2;
			else if(color!=a[lx][ly]) color=a[lx][ly],money++;
			if(money>=tu[lx][ly]) continue;
			tu[lx][ly]=money;
			q.push(cr(lx,ly,color,money));
		}
	}
//	for(int i=1;i<=m;i++){
//		for(int j=1;j<=m;j++) cout<<tu[i][j]<<" ";cout<<endl;
//	}
	if(tu[m][m]==1e8) printf("-1");
	else printf("%d",tu[m][m]);
}