制作不易，点个赞吧！来源：http://115.29.212.188/problem/CCF-1142
通用的BFS模板+记忆化 记忆点在于cost[MAX_SIZE][MAX_SIZE][3]， 3代表每个点不同颜色的最小值，仅仅是当这个点是无色的时候有效； 记忆化搜索其实没有通用的记忆点解决套路，通常的BFS只要记录1或者0,表示是否走过 需要根据题意找到每个点的唯一状态去记忆 就是要找到每个点的某种状态，我们肯定要使用最优，这题的状态点是color颜色题目：
NOIP201703棋盘时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 256MB，其他语言 512MB 难度：普及+/提高 分数：100 OI排行榜得分：16(0.1*分数+2*难度) 出题人：root
描述有一个 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 71 1 01 2 02 2 13 3 13 4 04 4 15 5 0 用例输出 1 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 枚金币。
【数据规模与约定】对30%的数据，1 ≤ m ≤ 5， 1 ≤ n ≤ 10。
对60%的数据，1 ≤ m ≤ 20， 1 ≤ n ≤ 200。
对100%的数据，1 ≤ m ≤ 100， 1 ≤ n ≤ 1,000。
答案来咯——————
#include using namespace std;//每个点需要记录cost（花费）和color（颜色），step不怎么需要，只是通用模板一般都记录步长typedef struct Node{int x,y;int step;int color;int cost;}Node; const int MAX_SIZE = 128;int mp[MAX_SIZE][MAX_SIZE]; //每个点输入的颜色记录int cost[MAX_SIZE][MAX_SIZE][3];//记忆点，通常的BFS只要记录1或者0,表示是否走过，本题是要记录cost(花费)int direct_x[4] = {1, -1, 0, 0};//四方向int direct_y[4] = {0,0, -1, 1}; //四方向int main(){int m, n;cin >> m >> n;for (int i = 0; i < n; i++){int a, b, c;cin >> a >> b >> c;mp[a][b] = c+1;}memset(cost, 0, sizeof(cost));//起点Node st = {1, 1, 0, mp[1][1], 1};Node ed = {m, m, 0, mp[m][m], 0};queue q;//q.push(起点)q.push(st);cost[1][1][mp[1][1]] = 1;int ans = INT_MAX;while(!q.empty()){//获得队列顶部元素，并删除Node top = q.front();q.pop();//如果是重点，记录一下最优值if (top.x == ed.x && top.y == ed.y){if (ans > top.cost)ans = top.cost;continue;}Node nxt;//点top -> 点nxt（这里按照题目进行4方向扩散）for (int i = 0; i < 4; i++){//Node nxt = top+方向; nxt.x = top.x + direct_x[i];nxt.y = top.y + direct_y[i];//nxt在地图范围内if (nxt.x < 1 || nxt.y < 1 || nxt.y > m || nxt.y > m) {continue;}//3种情况可以扩散到下个点//颜色相同，直接走if (top.color == mp[nxt.x][nxt.y]){nxt.color = mp[nxt.x][nxt.y];nxt.cost = top.cost;nxt.step = top.step + 1;//裁剪，同一个状态下之记录最优的情况去扩散if (cost[nxt.x][nxt.y][nxt.color] == 0 || nxt.cost < cost[nxt.x][nxt.y][nxt.color]){cost[nxt.x][nxt.y][nxt.color] = nxt.cost;q.push(nxt);}}//目标点是无色的，且上一个点并没有使用魔法else if (mp[nxt.x][nxt.y] == 0 && top.color == mp[top.x][top.y]){nxt.color = top.color;nxt.cost = top.cost + 2;nxt.step = top.step + 1;//裁剪，同一个状态下之记录最优的情况去扩散if (cost[nxt.x][nxt.y][nxt.color] == 0 || nxt.cost < cost[nxt.x][nxt.y][nxt.color]){cost[nxt.x][nxt.y][nxt.color] = nxt.cost;q.push(nxt);}}//目标点不是 白色，但是是跨颜色走else if (mp[nxt.x][nxt.y] != 0 && top.color != mp[nxt.x][nxt.y]){nxt.color = mp[nxt.x][nxt.y];nxt.cost = top.cost + 1;nxt.step = top.step + 1;//裁剪，同一个状态下之记录最优的情况去扩散if (cost[nxt.x][nxt.y][nxt.color] == 0 || nxt.cost < cost[nxt.x][nxt.y][nxt.color]){cost[nxt.x][nxt.y][nxt.color] = nxt.cost;q.push(nxt);}}}}if (ans != INT_MAX)cout