P3956棋盘

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int c[4]={1,0,0,-1};
int d[4]={0,1,-1,0};
int a[1001][1001];
bool v[1001][1001];
int b[1001][1001];
int n,m,ans=0x4ffff;
void dfs(int x,int y,int cnt,int r)
{
//	cout<<x<<" "<<y<<"\n";
	if(x==n&&y==n)
	{
		ans=min(ans,cnt);
		return ;
    }
	for(int i=0;i<4;i++)
	{
		int tx=x+c[i];
		int ty=y+d[i];
		if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&!v[tx][ty])
		{
			if(a[tx][ty]==a[x][y]&&a[tx][ty]!=0)
			{
				v[tx][ty]=1;
				dfs(tx,ty,cnt,0);
				v[tx][ty]=0;
			}
			if(a[tx][ty]!=a[x][y]&&a[tx][ty]!=0)
			{
				v[tx][ty]=1;
				dfs(tx,ty,cnt+1,0);
				v[tx][ty]=0;
				cnt--;
			}
			if(a[tx][ty]==0&&r==0)
			{ 
	            v[tx][ty]=1;
	            a[tx][ty]=a[x][y];
				dfs(tx,ty,cnt+2,1);
	            a[tx][ty]=0;
				v[tx][ty]=0;
				r=0;
				cnt-=2;
			}
		}
	}
	return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c;
	}
	dfs(1,1,0,0);
	if(ans==0x4ffff)
	cout<<-1;
	else
	cout<<ans<<"\n";
	return 0;
}