记录编号	507767	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017PJ]棋盘	最终得分	100
用户昵称	Chtholly	是否通过	通过
代码语言	C++	运行时间	0.119 s
提交时间	2018-09-03 08:59:16	内存使用	0.40 MiB

#include<bits/stdc++.h>
#define maxn 201
using namespace std;
int move[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int n,m,X,Y,T;
int min_value[maxn][maxn],color[maxn][maxn];
int total(int col ,int x ,int y){
	if(color[x][y]==col) return 0;
	if(color[x][y]==-1) return 2;
	return 1;
}
void dfs(int x,int y,int value,int jud){
	int next_x,next_y,next_value;
	if(value>=min_value[x][y]) return ;
	min_value[x][y]=value;
	if(x==m&&y==m) return ;
	for(int i=0;i<4;i++){
		next_x=x+move[i][0]; 
		next_y=y+move[i][1];
		next_value=value+total(color[x][y],next_x,next_y);
		if(next_x>=1&&next_y>=1&&next_x<=m&&next_y<=m){
			bool pd=0;
			if(next_value==value+2) 
				if(jud) continue;
				else pd=1,color[next_x][next_y]=color[x][y];
				dfs(next_x,next_y,next_value,pd);
				if(pd) color[next_x][next_y]=-1;
		}
	}
}
int main()
{
	freopen("checkerboard.in","r",stdin);
	freopen("checkerboard.out","w",stdout);
	scanf("%d%d",&m,&n);
	memset(color,-1,sizeof(color));
	memset(min_value,0x7f,sizeof(min_value));
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&X,&Y,&T),color[X][Y]=T;
	dfs(1,1,0,0);
	if(min_value[m][m]>200000) cout<<"-1";
	else cout<<min_value[m][m];
	return 0;
}
/*
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
*/