代码如下:
#include "bits/stdc++.h"
using namespace std;
struct Unsigned{
int Color,Num;
}Map[110][110];
int NextX[4],NextY[4];
bool Visited[12110];
int Dis[12110],N,M;
struct EDGE{
int Next,To,Dis;
}E[12110];
int Head[12110],Size;
void Made(void){
NextX[1]=1;NextY[1]=0;
NextX[2]=-1;NextY[2]=0;
NextX[3]=0;NextY[3]=1;
NextX[4]=0;NextY[4]=-1;
return;
}
void EDGE_Add(int From,int To,int Dis){
E[++Size].Next=Head[From];
E[Size].Dis=Dis;
Head[From]=Size;
E[Size].To=To;
return;
}
bool Judge(int X,int Y){
if(X<1||X>N)return true;
if(Y<1||Y>N)return true;
return false;
}
void Add(int FromX,int FromY){
if(Map[FromX][FromY].Color==0)
return;
for(register int i=1;i<=4;i++){
int ToX=FromX+NextX[i];
int ToY=FromY+NextY[i];
if(Judge(ToX,ToY)==true)
continue;
if(Map[ToX][ToY].Color>0){
if(Map[ToX][ToY].Color==Map[FromX][FromY].Color)
EDGE_Add(Map[FromX][FromY].Num,Map[ToX][ToY].Num,0);
if(Map[ToX][ToY].Color!=Map[FromX][FromY].Color)
EDGE_Add(Map[FromX][FromY].Num,Map[ToX][ToY].Num,1);
continue;
}
for(register int j=1;j<=4;j++){
int GoX=ToX+NextX[j];
int GoY=ToY+NextY[j];
if(GoX==FromX&&GoY==FromY)
continue;
if(Judge(GoX,GoY)==true)
continue;
if(Map[GoX][GoY].Color==0)
continue;
if(Map[GoX][GoY].Color==Map[FromX][FromY].Color)
EDGE_Add(Map[FromX][FromY].Num,Map[GoX][GoY].Num,2);
if(Map[GoX][GoY].Color!=Map[FromX][FromY].Color)
EDGE_Add(Map[FromX][FromY].Num,Map[GoX][GoY].Num,3);
}
}
return;
}
struct Priority{
int Data,Dis;
friend bool operator <(Priority Num1,Priority Num2){
Num1.Dis>Num2.Dis;
}
};
#define INF 1<<29//跑最短路
void Dijkstra(void){
priority_queue <Priority> Queue;
for(register int i=1;i<=Map[N][N].Num;i++)
Visited[i]=false,Dis[i]=INF;
//初始化所有点都未访问过
Dis[Map[1][1].Num]=0;//起点设置
Queue.push((Priority){Map[1][1].Num,0});
while(!Queue.empty()){
Priority Beg=Queue.top();
Queue.pop();
int From=Beg.Data;
if(Visited[From]==true)
continue;
Visited[From]=true;
for(register int i=Head[From];i;i=E[i].Next){
int To=E[i].To;
if(Dis[To]>Dis[From]+E[i].Dis){
Dis[To]=Dis[From]+E[i].Dis;
if(Visited[To]==false){
Queue.push((Priority){To,Dis[To]});
}
}
}
}
return;
}
int main(void){
cin>>N>>M;
for(register int i=1;i<=N+1;i++){
for(register int j=1;j<=N+1;j++){
if(j==1)Map[i][j].Num=Map[i-1][N].Num+1;
else Map[i][j].Num=Map[i][j-1].Num+1;
}
}//给二维表上的每一个点标号
for(register int i=1;i<=M;i++){
int X,Y,Z;
cin>>X>>Y>>Z;Z++;
Map[X][Y].Color=Z;
}//给二维表染色
Made();//四个方向
N++;
Map[N-1][N].Color=1;
Map[N][N-1].Color=2;
for(register int i=1;i<=N;i++)
for(register int j=1;j<=N;j++)
Add(i,j);//建图
Dijkstra();//跑一遍最短路
int Min=min(Dis[Map[N][N-1].Num],Dis[Map[N-1][N].Num]);
if(Min==INF)
cout<<"-1"<<endl;//如果无法到达,输出-1
else cout<<Min<<endl;//如果可以到达,输出答案
return 0;
}