记录编号	543555	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017PJ]棋盘	最终得分	100
用户昵称	没啥，随心	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2019-10-05 23:57:35	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
int m,n,d[1001][1001],xx[4]={1,0,-1,0},yy[4]={0,1,0,-1};
long long f[1001][1001],ans=9999999;
int js(int x,int y,int cl,int mf,int xj)
{
	if(x==m&&y==m)
	{
		if(xj<ans) ans=xj; 
		
	}
	else
{
	//cout<<x<<" "<<y<<" "<<f[x][y]<<" "; //调试 
	//cout<<f[m][m]<<endl;
	for(int i=0;i<4;i++)
	{
		int xxx=x+xx[i];
		int yyy=y+yy[i];
		if((xxx>=1&&xxx<=m)&&(yyy>=1&&yyy<=m)&&(xj<f[xxx][yyy]))
	{	
		if(d[xxx][yyy]>=0)
		{
		    if(cl==d[xxx][yyy])
		    {
				f[xxx][yyy]=xj;
				js(xxx,yyy,cl,0,xj);
			}
			else
			{
				//if(xj+1<f[xxx][yyy])
			    //{
				    f[xxx][yyy]=xj+1;
				    js(xxx,yyy,(cl+1)%2,0,xj+1);
			    //}
			}
		}
		else
		{
		if(mf==0&&xj+2<f[xxx][yyy])
		{
				f[xxx][yyy]=xj+2;
				js(xxx,yyy,cl,1,xj+2);
		}
		}
	}
	}
}
}
int nb(){
	freopen("checkerboard.in","r",stdin);
	freopen("checkerboard.out","w",stdout);
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	for(int j=1;j<=m;j++)
{
		d[i][j]=-1;
		f[i][j]=9999999;
}
	for(int i=1;i<=n;i++)
{
	int a,b,c;
	cin>>a>>b>>c;
	d[a][b]=c;
}
    js(1,1,d[1][1],0,0);
    
    if(ans==9999999) cout<<"-1";
    else
    cout<<ans;
}
int bbc=nb();
int main(){
	;
}