题目描述

有一个m × m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。

另外，你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。

现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？

输入描述:

数据的第一行包含两个正整数 m，n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的 n 行，每行三个正整数 x，y，c，分别表示坐标为（x，y）的格子有颜色 c。其中 c=1代表黄色，c=0 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标为（1,1），右下角的坐标为（m, m）。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（1，1）一定是有颜色的。

输出描述:

输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出-1。

示例1

输入
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
输出
8
说明

从（1，1）开始，走到（1，2）不花费金币从（1，2）向下走到（2，2）花费 1枚金币从（2，2）施展魔法，将（2，3）变为黄色，花费 2 枚金币从（2，2）走到（2，3）不花费金币从（2，3）走到（3，3）不花费金币从（3，3）走到（3，4）花费 1 枚金币从（3，4）走到（4，4）花费 1 枚金币从（4，4）施展魔法，将（4，5）变为黄色，花费 2枚金币，从（4，4）走到（4，5）不花费金币从（4，5）走到（5，5）花费 1 枚金币共花费 8枚金币。

示例2

输入
5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0
输出
-1
说明

从（1，1）走到（1，2），不花费金币从（1，2）走到（2，2），花费 1金币施展魔法将（2，3）变为黄色，并从（2，2）走到（2，3）花费 2金币从（2，3）走到（3，3）不花费金币

从（3，3）只能施展魔法到达（3，2），（2，3），（3，4），（4，3）

而从以上四点均无法到达（5，5），故无法到达终点，输出－1


备注:

对于 30%的数据，1≤m ≤5， 1 ≤ n ≤ 10。
对于 60%的数据，1≤m ≤20， 1 ≤ n ≤ 200。
对于 100%的数据，1 ≤ m ≤ 100， 1 ≤ n ≤ 1,000。

解答

方法：记忆化广度优先搜索（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)的颜色增加步数即可；
4、(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;
}


来源：ingu