P3956 [NOIP2017 普及组] 棋盘

之前用 dfs 过了，今天突然想用 bfs，结果就 WA 70 了……错误的答案都是比答案小 1，求调

#include <bits/stdc++.h>
using namespace std;
#define int long long

int m, n, mp[110][110], vis[110][110];
//             上  下  左  右
int px[] = {0, -1, 1,  0,  0};
int py[] = {0, 0,  0,  -1, 1};
struct XY {
	int x, y, c;
};
queue<XY> qu;

int bfs(XY s) {
	memset(vis, 0x3f, sizeof(vis));
	qu.push(s), vis[s.x][s.y] = 0;
	while(qu.size()) {
		XY u = qu.front(); qu.pop();
		if(u.x == m && u.y == m) return vis[u.x][u.y];
		for(int i = 1; i <= 4; i++) {
			int tx = u.x+px[i], ty = u.y+py[i];
			if(tx < 1 || ty < 1 || tx > n || ty > n) continue;
			if(!mp[u.x][u.y] && !mp[tx][ty]) continue;
			else if(!mp[u.x][u.y] && mp[tx][ty]) {
				int w = 0;
				if(u.c != mp[tx][ty]) w = 1;
				if(vis[u.x][u.y]+w >= vis[tx][ty]) continue;
				vis[tx][ty] = vis[u.x][u.y]+w;
				qu.push({tx, ty, mp[tx][ty]});
			}
			else if(mp[u.x][u.y] && !mp[tx][ty]) {
				if(vis[u.x][u.y]+2 >= vis[tx][ty]) continue;
				vis[tx][ty] = vis[u.x][u.y]+2;
				qu.push({tx, ty, mp[u.x][u.y]});
			}
			else if(mp[u.x][u.y] != mp[tx][ty]) {
				if(vis[u.x][u.y]+1 >= vis[tx][ty]) continue;
				vis[tx][ty] = vis[u.x][u.y]+1;
				qu.push({tx, ty, mp[tx][ty]});
			}
			else if(mp[u.x][u.y] == mp[tx][ty]) {
				if(vis[u.x][u.y] >= vis[tx][ty]) continue;
				vis[tx][ty] = vis[u.x][u.y];
				qu.push({tx, ty, mp[tx][ty]});
			}
		}
	}
	return -1;
}

signed main() {
    scanf("%lld%lld", &m, &n);
	for(int i = 1; i <= n; i++) {
		int x, y, c;
		scanf("%lld%lld%lld", &x, &y, &c);
		mp[x][y] = c+1;
	}
	printf("%lld\n", bfs({1, 1, mp[1][1]}));
	/*for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= m; j++)
			if(vis[i][j] < 1000000) cout << vis[i][j] << ' ';
			else cout << "∞ ";
		cout << endl;
	}*/

    return 0;
}