#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int x,y,c,i,j,m,n,minn=99999999;
int grid[1005][1005],a[1005][1005];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y,int sum)
{   
    if(sum>minn)return;
	if(x<=0||y<=0||x>m||y>m||grid[x][y]==-2)return;
	if(sum>a[x][y])return;
	a[x][y]=sum;//剪枝
	if(x==m&&y==m)
	{   
	    //cout<<sum<<endl;
		minn=min(sum,minn);
		return;
	}
	int tmp=grid[x][y],k;
	grid[x][y]=-2;
	for(k=0;k<4;k++)
	{
		int xx=x+dx[k];
		int yy=y+dy[k];
		if(grid[xx][yy]==-1&&tmp!=2&&tmp!=3)
		{   
			grid[xx][yy]=tmp+2;
			dfs(xx,yy,sum+2);
			grid[xx][yy]=-1; 
		}
		else if(grid[xx][yy]==tmp||grid[xx][yy]==tmp+2||grid[xx][yy]==tmp-2)
			dfs(xx,yy,sum);
		else if(grid[xx][yy]!=tmp&&grid[xx][yy]!=-1) 
		    dfs(xx,yy,sum+1);
	}
	grid[x][y]=tmp;
}
int main()
{   
    memset(a,127/3,sizeof(a));
	scanf("%d%d",&m,&n);
	for(i=1;i<=m;i++)
	    for(j=1;j<=m;j++)
	        grid[i][j]=-1;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		grid[x][y]=c;
	}
	dfs(1,1,0);
	if(minn==99999999)printf("
    -1");
	else printf("%d",minn);
} 

好多题解用的都是这个思路啊