0.题目描述
有一个的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 个金币。
你可以花费 个金币将一个无色格子暂时变成指定的颜色，但是在到达一个原本就有颜色的格子前不能再次使用，离开该格子后颜色恢复。
求最少花费的金币数。
本来的描述就挺简洁的，所以大部分引用的原题的描述
1. 心路历程
本来我看到这个格子，还是从左上角到右下角，直接满脑子都是 dp，，然后才发现他不一定要按拓扑序走才是最短的，所以正解是搜索(最短路)，然后搜索写了四个版本，最后发现第一个(最暴力的那个)思路是对的，毕竟数据只有 。
2. 解析
2.1 前言
- 那个 dp 的错误思想就不多说了，想看的可以看一下代码，这个思路只能应付部分按照拓扑序走的情况。
- 因为正解就是暴力，暴力就是正解，所以这个题的代码量不算太小，而且需要头脑清醒
2.2 思路
-
把能走的路全部建一条边，边权是走过去消耗的金币数，然后对生成的图跑 Dijkstra。
简单的一句话，但是实现起来缺不太容易
2.3 实现
-
点如何编号
如图，把每一行都接上，顺着编号。
从坐标对应到编号的函数:
int tonum(const int &x, const int &y) { return n * (x - 1) + y; }从编号对应到坐标的函数:
pair<int, int> tosite(const int &x) { return {ceil((double)x / n), x % n == 0 ? n : x % n}; } -
建边逻辑 (强烈建议单独写一个函数)
以样例为例 ，看上面的图
设入点为 ，出点为 。
颜色() : 为无色， 为红色， 为黄色。
- 且 由于不能连续施展魔法所以不能走，不建边。 和
- 且 可以消耗两个金币施展魔法将 变成 ，建边，边权为 。 和
- 且 如果能走，则 已经被施展魔法，颜色取决于给 施展魔法的点，建边，边权为 ，在求最短路时特判。 和
- 且
- 可以直接走，建边，边权为 。 和
- 可以消耗一个金币走，建边，边权为 。 和
-
Dijkstra
大部分套模板就行，需要特判一下建边的情况 3，在队列的参数里面加一项，记录父节点，当搜到一个边权为 的边时对比它和它的隔代祖先节点的颜色，决定将 改成是 还是 ，相当于是转化成了建边的情况 4。
3.总结
这个看似简单的暴力题细节特别多，不要太小看他了，一定要保持清醒
Ac Code
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
const int N = 110;
const int M = 40010;
int c[N][N]; // 记录颜色
int nxt[M], ver[M], w[M], head[M]; // 存图
int tot;
int n, m;
void add(int x, int y, int e) {
ver[++tot] = y;
w[tot] = e;
nxt[tot] = head[x];
head[x] = tot;
}
int tonum(const int &x, const int &y) { // 坐标转到序号
return n * (x - 1) + y;
}
pair<int, int> tosite(const int &x) { // 序号转到坐标
// 这里要注意，稍不留神就错了，主要是取模的问题，本来是5的会被模成0，注意特判
return {ceil((double)x / n), x % n == 0 ? n : x % n};
}
int tocol(const int &x) { // 序号转到颜色
return c[tosite(x).first][tosite(x).second];
}
bool judge(const int &x, const int &y) { // 判断是否出界
return x > 0 && x <= n && y > 0 && y <= n;
}
void build(const int &a, const int &b, const int &x, const int &y) { // 难点:建边
if (c[a][b] == -1 && c[x][y] == -1) return; // 两个没有颜色，只能变一个，所以不能走
else if (c[x][y] == -1) add(tonum(a, b), tonum(x, y), 2); // 有 -> 无 消耗2个金币
else if (c[a][b] == -1) add(tonum(a, b), tonum(x, y), -1); // 无 -> 有 视情况而定，先弄成-1到时候再判断
else if (c[a][b] == c[x][y]) add(tonum(a, b), tonum(x, y), 0); // 颜色相同，消耗0个金币
else add(tonum(a, b), tonum(x, y), 1); // 颜色不同，消耗1个金币
}
int dijkstra(const int &s, const int &t) {
priority_queue<piii, vector<piii>, greater<piii> > q; // pair<距离, <编号，父节点> >
int d[M];
bool v[M];
memset(d, 0x3f, sizeof(d));
memset(v, 0, sizeof(v));
d[s] = 0;
q.push({0, {s, 0}});
while (!q.empty()) {
int x = q.top().second.first;
int fa = q.top().second.second;
q.pop();
if (v[x]) continue;
v[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int &y = ver[i];
int t = w[i];
// 之前特殊标记的，y与x的父节点(y的隔代祖先)颜色相同则消耗0个，不同则消耗1个
// 默认把没颜色的节点标记成其父节点的颜色，方便统计
if (w[i] == -1) {
if (tocol(fa) != tocol(y)) {
t = 1;
}
else t = 0;
}
// 正常的dijkstra的状态转移
if (d[y] > d[x] + t) {
d[y] = d[x] + t;
q.push({d[y], {y, x}});
}
}
}
return d[t] == 0x3f3f3f3f ? -1 : d[t]; // 注意特判不能到达的情况
}
int main() {
memset(c, -1, sizeof(c));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
c[x][y] = z;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
// 建边，注意判断有没出界
if (judge(i + 1, j)) build(i, j, i + 1, j);
if (judge(i, j + 1)) build(i, j, i, j + 1);
if (judge(i - 1, j)) build(i, j, i - 1, j);
if (judge(i, j - 1)) build(i, j, i, j - 1);
}
}
printf("%d\n", dijkstra(1, tonum(n, n)));
return 0;
}