```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXM = 105;
int mmap[MAXM][MAXM],m,n;
int ans[MAXM][MAXM];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
typedef struct Node{
int x,y,color;
}Node;
Node Create(int x,int y,int color){
Node create;
create.x = x;
create.y = y;
create.color = color;
return create;
}
void init(){
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
ans[i][j] = -1;
mmap[i][j] = -1;
//cout << ans[i][j] << ' ';
}
//cout << "\n";
}
}
bool outofrange(int x,int y){
return x <= 0 || y <= 0 || x > m || y > m;
}
void bfs(){
queue<Node> q;
q.push(Create(1,1,mmap[1][1]));
Node nowtop,tonode;
int nowcost,nowcolor,tocolor;
while(!q.empty()){
nowtop = q.front();
q.pop();
//cout << nowtop.x << ' ' << nowtop.y << ' ' << nowtop.color <<"\n";
for(int i = 0; i <= 3; i++){
tonode = Create(nowtop.x + dx[i],nowtop.y + dy[i],mmap[nowtop.x + dx[i]][nowtop.y + dy[i]]);
nowcolor = mmap[nowtop.x][nowtop.y];
tocolor = mmap[tonode.x][tonode.y];
if(!outofrange(tonode.x,tonode.y)){
if(nowcolor != -1 && tocolor != -1){
if(nowtop.color == tocolor) nowcost = 0;
else nowcost = 1;
if(ans[tonode.x][tonode.y] == -1 || (ans[tonode.x][tonode.y] > ans[nowtop.x][nowtop.y] + nowcost)){
ans[tonode.x][tonode.y] = ans[nowtop.x][nowtop.y] + nowcost;
q.push(Create(tonode.x,tonode.y,tocolor));
}
}
else if(nowcolor != -1 && tocolor == -1){
nowcost = 2;
tocolor = nowcolor;
if(ans[tonode.x][tonode.y] == -1 || (ans[tonode.x][tonode.y] > ans[nowtop.x][nowtop.y] + nowcost)){
ans[tonode.x][tonode.y] = ans[nowtop.x][nowtop.y] + nowcost;
q.push(Create(tonode.x,tonode.y,tocolor));
}
}
else if(nowcolor == -1 && tocolor != -1){
if(nowtop.color == tocolor) nowcost = 0;
else nowcost = 1;
if(ans[tonode.x][tonode.y] == -1 || (ans[tonode.x][tonode.y] > ans[nowtop.x][nowtop.y] + nowcost)){
ans[tonode.x][tonode.y] = ans[nowtop.x][nowtop.y] + nowcost;
q.push(Create(tonode.x,tonode.y,tocolor));
}
}
}
}
}
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin >> m >> n;
init();
int nowx,nowy,nowcolor;
for(int i = 1; i <= n; i++){
cin >> nowx >> nowy >> nowcolor;
mmap[nowx][nowy] = nowcolor;
}
ans[1][1] = 0;
//cout << "\n";
bfs();
cout << ans[m][m];
return 0;
}
```
这是没在队列里记录当前花费的代码，只有70分
by ZhuHua14 @ 2023-12-21 19:37:01
该代码被如下数据HACK
in：
```
10 20
1 1 0
1 5 1
2 2 0
2 4 1
3 2 0
3 3 1
4 2 0
4 4 1
5 1 1
5 2 1
5 5 0
6 5 0
7 8 0
7 6 1
8 6 0
8 8 1
9 10 1
9 7 1
9 9 0
10 9 0
```
应当输出：
```
20
```
该份代码输出：
```
19
```
by ZhuHua14 @ 2023-12-21 19:38:59
@[ZhuHua14](/user/826012) 感谢 Hack，已经过了
by Side_sdtkwxt @ 2024-01-21 13:08:30
6
by WAI_kycm @ 2024-01-30 10:16:15
我的理解是，ans数组存储的只是最小消耗，但是如果产生最小消耗的选择最后是无效的，那么ans数组中的值也应该被舍去，所以每一步存储消耗，需要与每一步的消耗进行比较较小。
如理解错误，望指正
by yahuac @ 2024-04-09 23:55:56