```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int read(){
int a=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') a=a*10+c-'0',c=getchar();
return a;
}
int ans=-1;
int alpha[4][2]={
1,0,
-1,0,
0,1,
0,-1
};
int m=read(),n=read();
int t[N][N],t1[N][N];
void dfs(int sum,int x,int y,bool used){
//cout<<x<<' '<<y<<' '<<sum<<endl;
if(x==0||x>m||y==0||y>m) return ;
if(t1[x][y]<=sum) return;
t1[x][y]=sum;
if(x==m&&y==m){
ans=sum;
return ;
}
for(int i=0;i<4;i++){
int x1=x+alpha[i][0],y1=y+alpha[i][1];
if(t[x1][y1]){
if(t[x1][y1]==t[x][y])
dfs(sum,x1,y1,0);
else
dfs(sum+1,x1,y1,0);
}
else if(used==0){
t[x1][y1]=t[x][y];
dfs(sum+2,x1,y1,1);
t[x1][y1]=0;
}
}
}
int main(){
for(int i=1;i<=n;i++){
int x=read(),y=read(),c=read();
if(c==1) t[x][y]=2;
else t[x][y]=1;
//cout<<x<<' '<<y<<' '<<t[x][y]<<endl;
}
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++) t1[i][j]=1e9+5;
dfs(0,1,1,0);
cout<<ans<<endl;
return 0;
}
```
下次记得把调试删完。。。
by crescentic @ 2020-09-21 21:30:12
阿哲
by AdGats @ 2020-09-21 21:42:59