#include<bits/stdc++.h>
#define int long long
using namespace std;
const int dx[] = { 0, 0, 1, -1 } ;
const int dy[] = { 1, -1, 0, 0 } ;
int m , n, a [105] [105], ans [105] [105];
struct node {
	int x;
	int y;
	int color;
	int cur;
};
queue<node> st;
signed main(){
	cin >> n >> m;
	for ( int i = 1 ;i <= m; i++) {
		int kk1 , kk2 , kk3;
		cin >> kk1 >> kk2 >> kk3;
		a [kk1] [kk2] = kk3 + 1;
		
	}
	memset ( ans, 0x3f, sizeof ( ans ));
	ans [1] [1] = 0;
	st . push(node { 1, 1 , a [1] [1] ,0});
	while (st.size()) {
		node t = st .front ();
		st.pop();
		int x = t . x;
		int y = t . y;
		int color = t . color;
		int cur = t . cur;
		for (int i = 0 ;i <= 3 ; i ++) {
			int xx = x + dx [i] ;
			int yy = y + dy [i] ;
			if ( a [xx] [yy] ) {
				int k = cur + ( a[xx] [yy] != color);
				if ( ans [xx] [yy] > k) {
					ans [xx] [yy] =k;
					st . push(node { xx, yy, a [xx] [yy] ,k});
				}
			}
			else if ( a [x] [y]) {
				int k = ans [x] [y] + 2;
				if ( ans [xx] [yy] > k) {
					ans [xx] [yy] =k;
					st . push(node { xx, yy, a [xx] [yy] ,k});
				}
 			}
		}
	}
	cout << ans [n] [n];
	return 0;
}

样例不过。

提交全部RE