题解 | #[NOIP2017]棋盘#

题目大意：

（1）从地图左上角走到右下角，不能斜着走
（2）有红、黄两种颜色的格子。相邻颜色格子，同颜色不用花钱，不同颜色要花1个金币
（3）遇到无颜色（白色）格子，可用一次魔法使其有红、黄中任意一种颜色，但不能连续使用。使用一次需花2个金币
（4）求出整个过程最小费用

思路分析：

（1）有图有格子，我们想到bfs(最为经典）
（2）**最关键的一点** ：这和普通的bfs不同，并不是要找第一个到达终点的路线的费用，而是要找花费最少的费用，因此在到达终点后不能直接结束程序。这涉及到要多次访问同一个点，因此用一个数组val来存储每个点的最小花费，故称之为“记忆化搜索”。（上面的dalao也讲述过，本弱鸡只做通俗解释）
（3）bfs队列存储元素：x,y坐标、当前格子最小值、当前格子颜色。注意，由于可能出现多次访问某些点的情况，假若其中一些点无色，便会弄乱地图。因此我们要将每一步颜色存入对应的在队列中的位置，然后用原本的输入数组map记录原始的颜色
（4）bfs的判断条件：
		大条件：没有越界。
        1.当访问到的格子有颜色：
          跟新本点最小花费：是否更优解为上个点最小花费（val[beforex][beforey])加上每格花费
          val[nowx][nowy]=min(val[nowx][nowy], val[beforex][beforey]+abs(map[nowx][nowy]-map[beforex][beforey]))
          再存入队列即可
        2.当访问到的格子无颜色：
          若上个格子无颜色，则不成立（通过查看原始图map）
          否则：更新本点最小花费，类似于上面的
          val[nowx][nowy]=min(val[nowx][nowy],val[beforex][beforey]+2)
          再存入队列。注意存入颜色为上一个格子的颜色，因为这是贪心最优解（想想为什么）

易错指南：

本题用动态规划更新每个点很麻烦，因为本题在图上行走的方向可以是4个，而动态规划的一般适用于2个方向。

满分代码：

#include <cstdio>
#include <queue> 
#include <cmath>

using namespace std;

const int INF = 0x7ffffff;
const int N = 105;
struct T {
	int xp, yp, v, c;
	//x,y坐标,价格,颜色 
};

int m, n, x, y, c;
int a[N][N], val[N][N], ans = -1; 
// a数组存储原图，相当于前面说明的map
// val存储最小花费
int dx[4] = {1, -1, 0, 0};
int	dy[4] = {0, 0, 1, -1};
queue<T> Q;

void bfs() {
	val[1][1] = 0;
	Q.push(T{1, 1, 0, a[1][1]});
	while (!Q.empty()) {
		T head = Q.front();
		Q.pop();
		int bx = head.xp, by = head.yp;
		int bv = head.v, bc = head.c;
		// 上一个访问点的x,y坐标、最小花费和颜色
		for (int i = 0; i < 4; i++) {
			int cx = bx + dx[i];
			int cy = by + dy[i];
            // cx,cy为目前站在的点的x,y坐标
			if (cx > 0 && cy > 0 && cy <= m && cy <= m) {// 是否越界
				if (a[cx][cy]){
					if (val[cx][cy] > bv + abs(bc - a[cx][cy])) {// 更新最小花费
						val[cx][cy] = bv + abs(bc - a[cx][cy]);
						Q.push(T{cx, cy, val[cx][cy], a[cx][cy]});
					}
				}
				else {
					if (!a[bx][by]) continue ;
					if (val[cx][cy] > bv + 2) {// 同上
						val[cx][cy] = bv + 2;
						Q.push(T{cx, cy, val[cx][cy], bc});
					}
				}
			}
		}
	}
	if (val[m][m] != INF) ans = val[m][m];
    // 若能够到达终点
	return ;
}

int main() {
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d", &x, &y, &c);
		a[x][y] = c + 1;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			val[i][j] = INF;
		}
	}
	
	bfs();
	
	printf("%d", ans);
}

写在最后：

这篇题解是本弱鸡写的第一篇题解，望各位大佬帮忙指点指点，同时也希望大家多多鼓励，谢谢！