一开始自己写的代码，DFS剪枝后65分

修改时参考的题解

#include<bits/stdc++.h>
using namespace std;
/*====================*/
using lnt=long long;
/*====================*/
const int INF=0X3F3F3F3F;
/*====================*/
const int N=1e3+10;
/*====================*/
int n,m;
int col[N][N];
/*====================*/
/*====================*/
int ans=INF;
int f[N][N];
bool vis[N][N];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
void DFS(const int x,const int y,const bool magic=true,const int use=0,const int xcol=-1)
{
//	printf("(%d,%d) col:%d magic:%d use:%d xcol:%d\n",x,y,col[x][y],magic,use,xcol);
	if(use>=ans) return;
	if(use>f[x][y]) return;
	//
	f[x][y]=use;
	vis[x][y]=true;
	if(x==n&&y==n) return;
	//
	for(int i=0;i<4;++i)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<1||xx>n||yy<1||yy>n) continue;
		if(vis[xx][yy]) continue;
		if(col[xx][yy]==0)
		{
			if(magic)
			{
				DFS(xx,yy,false,use+2,col[x][y]);
			}
		}
		else if(col[x][y]==col[xx][yy]||xcol==col[xx][yy])
		{
			DFS(xx,yy,true,use);
		}
		else
		{
			DFS(xx,yy,true,use+1);
		}
	}
	//
	vis[x][y]=false;
}
/*====================*/
void Solve(void)
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int x,y,c; cin>>x>>y>>c;
		if(c==1) col[x][y]=1;
		else col[x][y]=2;
	}
	//
	memset(f,INF,sizeof(f));
	DFS(1,1,true,0,-1);
	//
	if(f[n][n]==INF) cout<<-1;
	else cout<<f[n][n];
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r+",stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	int T=1; //cin>>T;
	while(T--) Solve();
	return 0;
}

提交记录