[noip 2017 普及组] 棋盘

0.题目描述#

题面:P3956 [NOIP2017 普及组] 棋盘

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

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

你可以花费 $2$ 个金币将一个无色格子暂时变成指定的颜色，但是在到达一个原本就有颜色的格子前不能再次使用，离开该格子后颜色恢复。

求最少花费的金币数。

~~本来的描述就挺简洁的，所以大部分引用的原题的描述~~

1. 心路历程#

本来我看到这个格子，还是从左上角到右下角，直接满脑子都是 dp，然后写了一大堆只有 $50$ 分，然后才发现他不一定要按拓扑序走才是最短的，所以正解是搜索(最短路)，然后搜索写了四个版本，最后发现第一个(最暴力的那个)思路是对的，毕竟数据只有 $100*100$ 。

2. 解析#

2.1 前言#

那个 dp 的错误思想就不多说了，这个思路只能应付部分按照拓扑序走的情况。
因为正解就是暴力，暴力就是正解，所以这个题的代码量不算太小，而且需要头脑清醒

2.2 思路#

把能走的路全部建一条边，边权是走过去消耗的金币数，然后对生成的图跑 Dijkstra。

简单的一句话，但是实现起来缺不太容易

2.3 实现#

点如何编号

如图，把每一行都接上，顺着编号。

从坐标对应到编号的函数:

1
int tonum(const int &x, const int &y) {
2
    return n * (x - 1) + y;
3
}

从编号对应到坐标的函数:

1
pair<int, int> tosite(const int &x) {
2
    return {ceil((double)x / n), x % n == 0 ? n : x % n};
3
}

**建边逻辑 **(强烈建议单独写一个函数)

以样例为例，看上面的图

设入点为 $x$ ，出点为 $y$ 。

颜色( $C$ ) : $-1$ 为无色， $0$ 为红色， $1$ 为黄色。
- $c_x=-1$ 且 $c_y=-1$ 由于不能连续施展魔法所以不能走，不建边 $eg.$ $3$ 和 $4$
- $c_x \neq -1$ 且 $c_y=-1$ 可以消耗两个金币施展魔法将 $c_y$ 变成 $c_x$ ，建边，边权为 $2$ 。 $eg.$ $2$ 和 $3$
- $c_x=-1$ 且 $c_y\neq-1$ 如果能走，则 $x$ 已经被施展魔法，颜色取决于给 $x$ 施展魔法的点，建边，边权为 $-1$ ，在求最短路时特判。 $eg.$ $8$ 和 $13$
- $c_x\neq-1$ $c_{x} \neq = - 1$ 且 $c_y\neq-1$ $c_{y} \neq = - 1$
  - $c_x=c_y$ 可以直接走，建边，边权为 $0$ 。 $eg.$ $1$ 和 $2$
  - $c_x\neq c_y$ 可以消耗一个金币走，建边，边权为 $0$ 。 $eg.$ $2$ 和 $7$
Dijkstra

大部分套模板就行，需要特判一下建边的情况 3，在队列的参数里面加一项，记录父节点，当搜到一个边权为 $-1$ 的边时对比它和它的隔代祖先节点的颜色，决定将 $-1$ 改成是 $0$ 还是 $1$ ，相当于是转化成了建边的情况 4。

3.总结#

这个看似简单的暴力题细节特别多，不要太小看他了，一定要保持清醒

Ac Code#

1
#include <cstdio>
2
#include <cstring>
3
#include <cmath>
4
#include <queue>
5

6
using namespace std;
7

8
typedef pair<int, int> pii;
9
typedef pair<int, pii> piii;
10

11
const int N = 110;
12
const int M = 40010;
13

14
int c[N][N]; // 记录颜色
15

16
int nxt[M], ver[M], w[M], head[M]; // 存图
17
int tot;
18

19
int n, m;
20

21
void add(int x, int y, int e) {
22
    ver[++tot] = y;
23
    w[tot] = e;
24
    nxt[tot] = head[x];
25
    head[x] = tot;
26
}
27

28
int tonum(const int &x, const int &y) { // 坐标转到序号
29
    return n * (x - 1) + y;
30
}
31

32
pair<int, int> tosite(const int &x) { // 序号转到坐标
33
    // 这里要注意，稍不留神就错了，主要是取模的问题，本来是5的会被模成0，注意特判
34
    return {ceil((double)x / n), x % n == 0 ? n : x % n};
35
}
36

37
int tocol(const int &x) { // 序号转到颜色
38
    return c[tosite(x).first][tosite(x).second];
39
}
40

41
bool judge(const int &x, const int &y) { // 判断是否出界
42
    return x > 0 && x <= n && y > 0 && y <= n;
43
}
44

45
void build(const int &a, const int &b, const int &x, const int &y) { // 难点:建边
46
    if (c[a][b] == -1 && c[x][y] == -1) return; // 两个没有颜色，只能变一个，所以不能走
47
    else if (c[x][y] == -1) add(tonum(a, b), tonum(x, y), 2); // 有 -> 无 消耗2个金币
48
    else if (c[a][b] == -1) add(tonum(a, b), tonum(x, y), -1); // 无 -> 有 视情况而定，先弄成-1到时候再判断
49
    else if (c[a][b] == c[x][y]) add(tonum(a, b), tonum(x, y), 0); // 颜色相同，消耗0个金币
50
    else  add(tonum(a, b), tonum(x, y), 1); // 颜色不同，消耗1个金币
51
}
52

53
int dijkstra(const int &s, const int &t) {
54
    priority_queue<piii, vector<piii>, greater<piii> > q; // pair<距离, <编号，父节点> >
55
    int d[M];
56
    bool v[M];
57
    memset(d, 0x3f, sizeof(d));
58
    memset(v, 0, sizeof(v));
59
    d[s] = 0;
60
    q.push({0, {s, 0}});
61
    while (!q.empty()) {
62
        int x = q.top().second.first;
63
        int fa = q.top().second.second;
64
        q.pop();
65
        if (v[x]) continue;
66
        v[x] = 1;
67
        for (int i = head[x]; i; i = nxt[i]) {
68
            int &y = ver[i];
69
            int t = w[i];
70
            // 之前特殊标记的，y与x的父节点(y的隔代祖先)颜色相同则消耗0个，不同则消耗1个
71
            // 默认把没颜色的节点标记成其父节点的颜色，方便统计
72
            if (w[i] == -1) {
73
                if (tocol(fa) != tocol(y)) {
74
                    t = 1;
75
                }
76
                else t = 0;
77
            }
78
            // 正常的dijkstra的状态转移
79
            if (d[y] > d[x] + t) {
80
                d[y] = d[x] + t;
81
                q.push({d[y], {y, x}});
82
            }
83
        }
84
    }
85
    return d[t] == 0x3f3f3f3f ? -1 : d[t]; // 注意特判不能到达的情况
86
}
87

88
int main() {
89
    memset(c, -1, sizeof(c));
90
    scanf("%d%d", &n, &m);
91
    for (int i = 1; i <= m; ++i) {
92
        int x, y, z;
93
        scanf("%d%d%d", &x, &y, &z);
94
        c[x][y] = z;
95
    }
96
    for (int i = 1; i <= n; ++i) {
97
        for (int j = 1; j <= n; ++j) {
98
            // 建边，注意判断有没出界
99
            if (judge(i + 1, j)) build(i, j, i + 1, j);
100
            if (judge(i, j + 1)) build(i, j, i, j + 1);
101
            if (judge(i - 1, j)) build(i, j, i - 1, j);
102
            if (judge(i, j - 1)) build(i, j, i, j - 1);
103
        }
104
    }
105
    printf("%d\n", dijkstra(1, tonum(n, n)));
106
    return 0;
107
}

Star's Blog