【正经题解】棋盘

方法：记忆化广度优先搜索（ $MBFS$ )
首先看到从一个点跑到另外一个点，第一反应就是搜索了。可以使用 $DFS$ 或 $BFS$ ，这里选用 $BFS$ 。
$BFS$ 需要使用队列保存待查找的格子，这里还要明确都需要保存哪些信息，坐标（ $x$ , $y$ ) 、当前步数和当前格子颜色。
格子颜色是存在 $map$ 数组中的，为什么还有在队列中保存颜色呢？因为空白的格子是可以变色的。所以要将其颜色存进队列，而原色 需要保留作为验证。
本题的思维难点在于将哪些格子入队及如何入队问题，为了优化搜索，使用 $val$ 数组来记忆当前格子需要的步数。
从当前( $x$ , $y$ )出发四个方向( $dx$ , $dy$ )判断，待考查的格子是否越界，如不越界进入考查。一共分四种情况：
$1$ 、( $x$ , $y$ ) 与( $dx$ , $dy$ ) 原来都是红或黄的。这样相同颜色步数 $+0$ ，不用颜色步数 $+1$ ；
$2$ 、( $x$ , $y$ )原来是有红或黄 ( $dx$ , $dy$ )是白色的。这样需要施展一次魔法改变颜色，这里有一个贪心，改变的颜色和当前颜色相同；
$3$ 、( $x$ , $y$ )原来是白色的 ( $dx$ , $dy$ )是红或黄的。因为入队格子肯定是曾经有颜色的，所以判断( $x$ , $y$ )被涂的 颜色和( $dx$ , $dy$ )的颜色增加步数即可；
$2$ 、( $x$ , $y$ ) 与( $dx$ , $dy$ ) 原来都是白色的。因为魔法无法连续使用，所以，这种情况走不了；

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int map[105][105],val[105][105];
struct node{
    int x,y,c,v;
};
queue<node>q;
int main() {
    int m,n,di[4][2]={0,1,1,0,0,-1,-1,0},ans=0x7f7f7f7f;
    memset(map,-1,sizeof(map));
    memset(val,0x7f,sizeof(val));
    cin>>m>>n;
    for(int i=0;i<n;i++){
        int x,y,c;
        cin>>x>>y>>c;
        map[x][y]=c;
    }
    q.push((node){1,1,map[1][1],0});
    val[1][1]=0;
    while(!q.empty()){
        int x=q.front().x,y=q.front().y,c=q.front().c,v=q.front().v;
        if(v>ans){
            q.pop();
            continue;
        }
        if(x==m&&y==m){
            ans=min(ans,v);
            q.pop();
            continue;
        }
        for(int k=0;k<4;k++){
            int dx=x+di[k][0],dy=y+di[k][1];
            if(dx>0&&dy>0&&dx<=m&&dy<=m){
                int bc=map[x][y],dc=map[dx][dy],mv=val[dx][dy],dv;
                if(dc>=0&&bc>=0){
                    dv=v+(dc==bc?0:1);
                    if(mv>dv){
                        q.push((node){dx,dy,dc,dv});
                        val[dx][dy]=dv;
                    }
                }else if(dc<0&&bc>=0){
                    if(mv>v+2){
                        q.push((node){dx,dy,bc,v+2});
                        val[dx][dy]=v+2;
                    }
                }else if(dc>=0&&bc<0){
                    dv=v+(c==dc?0:1);
                    if(mv>dv){
                        q.push((node){dx,dy,dc,dv});
                        val[dx][dy]=dv;
                    }
                }
            }
        }
        q.pop();
    }
    if(ans==0x7f7f7f7f){
        cout<<"-1"<<endl;
    }else {
        cout<<ans<<endl;
    }
    return 0;
}