记录编号	540845	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017PJ]棋盘	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2019-08-31 16:52:52	内存使用	21.36 MiB

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1005;
	int ans=999999999,m,n,q,w,e,a[maxn][maxn],b[maxn][maxn],flag;
    int tx[4]={1,-1,0,0},ty[4]={0,0,1,-1},xx,yy; 
    void dfs(int x,int y,int z,int co,int use){
    	if(x==m&&y==m){flag=1;ans=min(ans,z);return;}
    	if(z>=b[x][y])return ;
    	if(z<b[x][y]) b[x][y]=z;
    	//cout<<x<<' '<<y<<' '<<z<<' '<<co<<' '<<use<<' ';
    	for(int i=0;i<=3;i++){
    	xx=x+tx[i];yy=y+ty[i];
    	if(xx>0&&yy>0&&xx<=m&&yy<=m){
    	if(a[xx][yy]==co)
    //	cout<<1<<endl,
    	dfs(xx,yy,z,co,0);
    	if((a[xx][yy]==1&&co==2)||(a[xx][yy]==2&&co==1))
    //	cout<<2<<endl,
    	dfs(xx,yy,z+1,a[xx][yy],0);
    	if(a[xx][yy]==0&&use==0)
    //	cout<<3<<endl,
    	dfs(xx,yy,z+2,co,1);}}}
    int main() {
    	freopen("checkerboard.in","r",stdin);
    	freopen("checkerboard.out","w",stdout);
   	
   	cin>>m>>n;//m_size n_color
   	for(int i=1;i<=n;i++){
   		cin>>q>>w>>e;
   		e++;
   		a[q][w]=e;}
   		for(int i=1;i<=m;i++)
   		for(int o=1;o<=m;o++)b[i][o]=2100000000;
   	dfs(1,1,0,a[1][1],0);
   	if(flag==1)cout<<ans;
   	else cout<<-1;
    	return 0;
    }