题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
const int _mod=80112002;

int n,m,T;
int s[105][105];
int dp[105][105];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node{
	int x,y,vis,ans;
};

bool operator<(node x,node y){
	return x.ans>y.ans;
}

void bfs(){
	priority_queue<node> q;
	int x,y,vis,ans,temp;
	x=1,y=1,vis=-1,ans=0;
	dp[x][y]=ans;
	q.push({x,y,vis,ans});
	while(!q.empty()){
		x=q.top().x;y=q.top().y;
		vis=q.top().vis;ans=q.top().ans;
		q.pop();
		if(dp[x][y]<ans)	continue;
		if(x==n&&y==n){
			cout<<ans<<endl;
			return ;
		}
		for(int i=0;i<4;i++){
			int xx=x+dir[i][0];
			int yy=y+dir[i][1];
			if(xx<1||xx>n||yy<1||yy>n)	continue;
			int ans1;
			if(s[xx][yy]==-1){
				if(vis!=-1)	continue;
				for(int j=0;j<=1;j++){
					ans1=ans+2;
					if(s[x][y]!=j){
						ans1++;
					}
					if(ans1<dp[xx][yy]){
						dp[xx][yy]=ans1;
						q.push({xx,yy,j,ans1});
					}
				}
			}else{
				if(vis==-1){
					if(s[xx][yy]==s[x][y]){
						ans1=ans;
					}else{
						ans1=ans+1;
					}
				}else{
					if(s[xx][yy]==vis){
						ans1=ans;
					}else{
						ans1=ans+1;
					}
				}
				if(ans1<dp[xx][yy]){
					dp[xx][yy]=ans1;
					q.push({xx,yy,-1,ans1});
				}
			}
		}
	}
	cout<<"-1"<<endl;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			s[i][j]=-1;
			dp[i][j]=20005;
		}
	}
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		s[a][b]=c;
	}
	bfs();
	return 0;
}