记录编号	522069	评测结果	AAAAAWAAAAAAAAAAAAAA
题目名称	[NOIP 2017PJ]棋盘	最终得分	95
用户昵称	Harry Potter	是否通过	未通过
代码语言	C++	运行时间	0.004 s
提交时间	2018-11-08 21:43:51	内存使用	0.39 MiB

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;
int m,n;
int i,j,s,use,mix=999999999;
int a[102][102]={0},b[102][102]={0};
void start(int i,int j,int s,int use)
{
	int b1[5]={-1,0,1,0},b2[5]={0,1,0,-1};
	int b3,b4;
	if(i==m&&j==m)
	{
		if(s<mix)
			mix=s;
		s=0;
	}
	else
	{
		for(int k=0;k<4;k++)
		{
			b3=i+b1[k];b4=j+b2[k];
			if(b3>=1&&b3<=m&&b4>=1&&b4<=m&&s<b[b3][b4])
			{
				b[b3][b4]=s;
			if(a[b3][b4]!=0)
			{
				use=0;
				if(a[b3][b4]==a[i][j])
					start(b3,b4,s,use);
				else
					if(a[b3][b4]!=a[i][j])
						start(b3,b4,s+1,use);
			}
			else
				if(use==0)
				{
					use=1;
					a[b3][b4]=a[i][j];
					start(b3,b4,s+2,use);
					a[b3][b4]=0;
					use=0;
				}
			}
		}
	}
}
int main()
{
	freopen("checkerboard.in","r",stdin);
	freopen("checkerboard.out","w",stdout);
	int x,y,z;
	cin>>m>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x>>y>>z;
		if(z==0)
			z=2;
		a[x][y]=z;
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=m;j++)
		{
			b[i][j]=999999999;
		}
	}
	start(1,1,0,0);
	if(mix==999999999)
		mix=-1;
	cout<<mix;
	return 0;
}