bfs好流行啊，后面还有一个被坑的。
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
bool flag=false;
int n,m;
int a[N][N],g[N][N];
bool book[N][N];
int np[4][2]={
{0,1},{1,0},{0,-1},{-1,0}
};
int ans=INF;
void dfs(int x,int y,int cost,bool magic){
if(cost>=g[x][y])
return;
g[x][y]=cost;
if(x==n&&y==n){
ans=min(ans,cost);
flag=true;
return;
}
for(int i=0;i<4;i++){
int nx=x+np[i][0],ny=y+np[i][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!book[nx][ny]){
if(a[nx][ny]){
if(a[x][y]==a[nx][ny]){
book[nx][ny]=true;
dfs(nx,ny,cost,false);
book[nx][ny]=false;
}
else{
book[nx][ny]=true;
dfs(nx,ny,cost+1,false);
book[nx][ny]=false;
}
}
else{
if(!magic){
a[nx][ny]=a[x][y];
book[nx][ny]=true;
dfs(nx,ny,cost+2,true);
a[nx][ny]=0;
book[nx][ny]=false;
}
}
}
}
}
int main(){
cin>>n>>m;
while(m--){
int x,y,l;
cin>>x>>y>>l;
if(l==1) a[x][y]=1;
else if(l==0) a[x][y]=2;
}
memset(g,0x3f,sizeof(g));
book[1][1]=true;
dfs(1,1,0,false);
if(!flag) ans=-1;
cout<<ans;
return 0;
}
```
by zhuruirong @ 2023-03-23 17:51:18