题解

我的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>

using namespace std;

int n,m,map[105][105],ans=0x3f3f3f3f3f,rm[110][110];
int dx[5]={0,0,0,-1,1};
int dy[5]={0,1,-1,0,0};


int min(int a,int b)
{
	return a<b?a:b;
}

void dfs(int x,int y,int sum,bool magic)
{
	if(x<1||y<1||x>m||y>m)
		return;
	if(x==m&&y==m)
	{
		ans=min(ans,sum);
		return;
	}
	if(sum>rm[x][y])
		return;
	rm[x][y]=sum;
	for(int i=1;i<=4;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(map[xx][yy])
		{
			if(map[x][y]==map[xx][yy])
				dfs(xx,yy,sum,false);
			if(map[x][y]!=map[xx][yy])
				dfs(xx,yy,sum+1,false);
		}
		else
		{
			/*if(magic)
				return;
			else */if(!magic)
			{
				magic=true;
				map[xx][yy]=map[x][y];
				dfs(xx,yy,sum+2,magic);
				map[xx][yy]=0;
			}
		}
	}
}

int main()
{
	memset(rm,0x3f,sizeof(rm));
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		map[x][y]=c+1;
	}
	dfs(1,1,0,0);
	cout<<(ans!=0x3f3f3f3f?ans:-1);
	return 0;
 }