传送门

#include<bits/stdc++.h>
using namespace std;
int m,head=1,tail=1;
int x,y,c,n;
int ans=INT_MAX;
int f[105][105];
bool vis[105][105];
struct node{
	int x,y,color,t,money;
}que[10010];
int stepx[4]={1,0,-1,0};
int stepy[4]={0,1,0,-1};
void bfs(){
	que[tail++]={1,1,f[1][1],0,0};
	vis[1][1]=1;
	while(head<tail){
		if(que[head].x==m&&que[head].y==m){
			ans=min(ans,que[head].money);
		}
		for(int i=0;i<4;i++){
			int xx=stepx[i]+que[head].x;
			int yy=stepy[i]+que[head].y;
			if(vis[xx][yy]==0&&xx<=m&&xx>=1&&yy<=m&&yy>=1){
				if(que[head].t==1&&f[xx][yy]==-1){
					continue;
				}
				if(f[xx][yy]!=-1){
					if(f[xx][yy]==que[head].color){
						que[tail++]={xx,yy,que[head].color,0,que[head].money};
					}
					else{
						que[tail++]={xx,yy,f[xx][yy],0,que[head].money+1};
					}
				}
				else{
					que[tail++]={xx,yy,que[head].color,1,que[head].money+2};
				}
				vis[xx][yy]=1;
			}
		}
		cout<<que[head].x<<" "<<que[head].y<<" "<<que[head].money<<endl;
		head++;
	}
}
int main(){
//	freopen("chess.in","r",stdin);
//	freopen("chess.out","w",stdout);
	scanf("%d%d",&m,&n);
	memset(f,-1,sizeof(f));
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&c);
		f[x][y]=c;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			cout<<setw(2)<<f[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	bfs();
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			cout<<setw(2)<<vis[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<(ans==INT_MAX?-1:ans);
	return 0;
}
/*
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
*/
/*
5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0
*/