https://www.cnblogs.com/violet-acmer/p/9827010.html
题解：
BFS
相关变量解释：
color[maxn][maxn];...................................color[ i ][ j ] : ( i , j )点的颜色，-1代表无色
dp[maxn][maxn];.......................................dp[ i ][ j ] : 从( 1 , 1 )点到( i , j )点需要花费的最少金币
magic[maxn][maxn];..................................magic[ i ][ j ] : 判断 ( i , j )点是否使用魔法
in[maxn][maxn];.........................................in[ i ][ j ] : 判断( i , j )点是否在队列中
具体步骤：
初始，将(1,1)点加入队列中；
(1):保存队头元素并弹出
(2):每次，判断当前点的上下左右点是否可以通过当前点使dp[ ][ ]变小，如果可以，更新dp[ ][ ],如果被更新的点不在队列中，加入队列
(3):重复(2)过程，直到队列为空
AC代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define P pair<int ,int >
#define mem(a,b) memset(a,b,sizeof a)
const int maxn=+; int m,n;
int color[maxn][maxn];
int dp[maxn][maxn];
bool marge[maxn][maxn];
bool in[maxn][maxn];
queue<P >myqueue;
int dx[]={-,,,};
int dy[]={,,-,};
bool isSat(int val)
{
return val >= &&val <= m;
}
void Solve()
{
dp[][]=;//初始化dp[1][1],并将其加入到队列中
myqueue.push(P(,));
while(!myqueue.empty())//步骤(3)
{
P p=myqueue.front();//步骤(1)
myqueue.pop();
in[p.first][p.second]=false;
for(int i=;i < ;++i)//步骤(2)
{
int x=p.first+dx[i];
int y=p.second+dy[i];
if(isSat(x) && isSat(y))
{
if(!marge[p.first][p.second])//如果当前点的未使用过魔法的，也就意味这当前点的颜色是本身就有的
{
if(!marge[x][y])//如果与当前点相邻的点(x,y)也为曾使用过魔法
{
if(color[x][y] != -)//如果点(x,y)有色，但并不是因为魔法而产生的
{
//如果当前点可以放缩dp[x][y]
if(dp[x][y] > dp[p.first][p.second]+(color[x][y] != color[p.first][p.second]))
{
dp[x][y]=dp[p.first][p.second]+(color[x][y] != color[p.first][p.second]);
if(!in[x][y])//被放缩的点(x,y)如果不在队列中，加入队列
in[x][y]=true,myqueue.push(P(x,y));
}
}
else//如果无色，通过使用魔法将其变为与当前点颜色相同的点，并被放缩了dp[][]
{
marge[x][y]=true;
color[x][y]=color[p.first][p.second];
dp[x][y]=dp[p.first][p.second]+;
if(!in[x][y])
in[x][y]=true,myqueue.push(P(x,y));
}
}
else if(dp[x][y] > dp[p.first][p.second]+)//如果点(x,y)在之前使用过魔法，就需要判断，当前为使用过魔法的点是否可以放缩dp[x][y]
{
dp[x][y]=dp[p.first][p.second]+;
color[x][y]=color[p.first][p.second];
if(!in[x][y])
in[x][y]=true,myqueue.push(P(x,y));
}
}
else if(!marge[x][y] && color[x][y] != -)//如果当前点的使用过魔法的，也就意味这当前点的颜色是通过魔法变来的，那么，只有当其临近点(x,y)含有的颜色是其本身就有的才有资格判断是否可以被放缩
{
if(dp[x][y] > dp[p.first][p.second]+(color[x][y] != color[p.first][p.second]))
{
dp[x][y]=dp[p.first][p.second]+(color[x][y] != color[p.first][p.second]);
if(!in[x][y])
myqueue.push(P(x,y)),in[x][y]=true;
}
}
}
}
}
printf("%d\n",dp[m][m] == INF ? -:dp[m][m]);
}
void Init()
{
mem(dp,INF);
mem(in,false);
mem(marge,false);
mem(color,-);
}
int main()
{
scanf("%d%d",&m,&n);
Init();
for(int i=;i <= n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
scanf("%d",&color[x][y]);
}
Solve();
}