状态分为两大类

1. 下一个块没有颜色 对于当前状态，有以下状态以及操作: (1) 当前踩的块是被施法过的，不能施法，继续寻找其他扩展块 (2) 当前踩的块没有被施法过，对下一个块染成和当前块一样的颜色，代价+2
2. 下一个块有颜色 对于当前状态，有以下状态以及操作: (1) 当前块与下一个块颜色相同，扩展且无需任何代价 (2) 当前块与下一个块颜色相同，扩展且无需任何代价

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,cost;
	bool flag;
	bool operator<(const node &aa) const
	{
		return cost>aa.cost;
	}
};

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int a[2001][2001];
bool vis[2001][2001];

priority_queue<node> q;

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c+1;
	}
	node begin;
	begin.x=1;begin.y=1;begin.cost=0;begin.flag=0;
	q.push(begin);
	vis[1][1]=1;
	while(!q.empty())
	{
		begin=q.top();
		q.pop();
		if(begin.x==n&&begin.y==n)
		{
			cout<<begin.cost<<endl;
			return 0;
		}
		for(int i=0;i<4;++i)
		{
			int nx=begin.x+dx[i];
			int ny=begin.y+dy[i];
			node next;
			if(nx>0&&nx<=n&&ny>0&&ny<=n&&vis[nx][ny]==0)
			{
				if(a[nx][ny]!=0) //有颜色
				{
					if(a[nx][ny]==a[begin.x][begin.y])
					{
						next.x=nx;next.y=ny;next.cost=begin.cost;next.flag=0;
						vis[nx][ny]=1;
						q.push(next);
					}
					else if(a[nx][ny]!=a[begin.x][begin.y])
					{
						next.x=nx;next.y=ny;next.cost=begin.cost+1;next.flag=0;
						vis[nx][ny]=1;
						q.push(next);
					}
				}
				else  //没颜色
				{
					if(begin.flag==0)
					{
						a[nx][ny]=a[begin.x][begin.y];
						next.x=nx;next.y=ny;next.cost=begin.cost+2;next.flag=1;
						vis[nx][ny]=1;
						q.push(next);
					}	
				}	
			}
		}
	}
	cout<<-1<<endl;
	return 0;
}

也是想了很久，加上学习队列，还看了看思路写的~~