已经2年了，这2年都没再看这道题，如今心血来潮，来看看曾经的自己有多菜。

好，切入正题。一直在听人讲，这道题用bfs，所以，就没多想dfs之类的直接就上了bfs。题目中言若下一步是空的话，就只能变色，且不能连续变色，所以我们设一个magic数组，1为能使用魔法，0为不能使用。然后可行性判断：

1.若超界，返回1；

2.若走过，返回1；

3.若下一个位置为空，当前又不能使用魔法，返回1；

否则，返回0；

然后分下一个位置是不是空来讨论

1.若不为空且当前与之相同，step继承；

2.若不为空且当前与之不同，step++；

3.若为空，把他变成当前颜色，step+=2；

大致思路就是这样，代码中我把color=0改成了2

这样方便判断一些（个人观点）

code

#include<bits/stdc++.h>
using namespace std;

const int maxn=110;

bool vis[maxn][maxn];
int c[maxn][maxn],n,m;
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};

struct node
{
    int x;
    int y;
    bool magic=1;
    int step=0;
    friend bool operator < (node n1,node n2)
    {
        return n1.step > n2.step;
    }
};

bool judge(node cur,int x,int y)
{
    if(x<1||y<1||x>m||y>m) return 1;
    if(vis[x][y]) return 1;
    if(c[x][y]==0&&cur.magic==0) return 1;
    return 0;
}

int bfs()
{
    priority_queue<node>q;
    node first;
    first.x=1;
    first.y=1;
    first.step=0;
    vis[1][1]=1;
    q.push(first);
    while(!q.empty())
    {
        node cur=q.top();
        q.pop();
        if(cur.x==m&&cur.y==m)
        return cur.step;
        for(int i=0;i<4;i++)
        {
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];
            if(judge(cur,nx,ny)) continue;
            if(c[nx][ny])
            {
                node nxt;
                nxt.x=nx;
                nxt.y=ny;
                nxt.magic=1;
                if(c[nx][ny]==c[cur.x][cur.y]) nxt.step=cur.step;
                else nxt.step=cur.step+1;
                q.push(nxt);
                vis[nx][ny]=1;
            }
            if(!c[nx][ny])
            {
                node nxt;
                nxt.x=nx;
                nxt.y=ny;
                nxt.magic=0;
                nxt.step=cur.step+2;
                c[nx][ny]=c[cur.x][cur.y];
                q.push(nxt);
                vis[nx][ny]=1;
            }
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d",&m,&n);
    memset(vis,0,sizeof vis);
    memset(c,0,sizeof c);
    for(int i=1;i<=n;i++)
    {
        int col,x,y;
        scanf("%d%d%d",&x,&y,&col);
        if(!col) col=2;
        c[x][y]=col;
    }
    printf("%d",bfs());
    return 0;
}