[NOIP 2017 普及组] 棋盘

GitHub 跳转原题关系图返回列表

把位置、当前颜色和是否刚施法作为状态，在四维状态图上做 Dijkstra 求最小花费。

OJ: luogu

题目 ID: P3956

难度:普及+/提高

标签:最短路图论模拟noip

日期: 2026-06-20 12:57

题意

给一个 m x m 棋盘，部分格子本来就有颜色，部分格子无色。

你要从 (1,1) 走到 (m,m)，每次只能上下左右移动。

如果走向本来就有颜色的格子：

同色花费 0
异色花费 1

如果走向无色格子：

必须先施法把它临时染色，花费 2
并且魔法不能连续使用

求最少花费，无法到达输出 -1。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 8;
const int INF = 1e9;

struct Node {
    int x, y;
    int color;
    int magic;
    int dist;

    bool operator < (const Node &other) const {
        return dist > other.dist;
    }
};

int board_size, colored_cnt;
int board[MAXM][MAXM];
int dista[MAXM][MAXM][2][2];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool in_board(int x, int y) {
    return x >= 1 && x <= board_size && y >= 1 && y <= board_size;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(board, -1, sizeof(board));

    cin >> board_size >> colored_cnt;
    for (int i = 1; i <= colored_cnt; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        board[x][y] = c;
    }

    if (board[1][1] == -1) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 1; i <= board_size; i++) {
        for (int j = 1; j <= board_size; j++) {
            for (int c = 0; c < 2; c++) {
                for (int s = 0; s < 2; s++) {
                    dista[i][j][c][s] = INF;
                }
            }
        }
    }

    // 小数据暴力版：直接在完整状态图上跑最短路。
    priority_queue<Node> pq;
    int start_color = board[1][1];
    dista[1][1][start_color][0] = 0;
    pq.push({1, 1, start_color, 0, 0});

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

        if (cur.dist != dista[cur.x][cur.y][cur.color][cur.magic]) continue;

        if (cur.x == board_size && cur.y == board_size) {
            cout << cur.dist << '\n';
            return 0;
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            if (!in_board(nx, ny)) continue;

            if (board[nx][ny] != -1) {
                int next_color = board[nx][ny];
                int cost = (cur.color == next_color ? 0 : 1);
                int new_dist = cur.dist + cost;
                if (new_dist < dista[nx][ny][next_color][0]) {
                    dista[nx][ny][next_color][0] = new_dist;
                    pq.push({nx, ny, next_color, 0, new_dist});
                }
                continue;
            }

            if (cur.magic == 1) continue;

            for (int next_color = 0; next_color <= 1; next_color++) {
                int new_dist = cur.dist + 2 + (cur.color != next_color);
                if (new_dist < dista[nx][ny][next_color][1]) {
                    dista[nx][ny][next_color][1] = new_dist;
                    pq.push({nx, ny, next_color, 1, new_dist});
                }
            }
        }
    }

    cout << -1 << '\n';
    return 0;
}

这题表面上像网格最短路，但一个格子不能只看坐标。

因为到达同一个格子时，后续决策还取决于两件事：

当前脚下格子的颜色是什么；
当前脚下格子是不是刚用魔法临时染出来的。

所以状态要写成：

(x, y, color, magic)

其中：

color 表示当前所在格的颜色；
magic = 1 表示当前格子是临时染色格；
magic = 0 表示当前格子本来就有颜色。

接下来分两类转移。

第一类，下一格本来就有颜色。

设下一格颜色是 next_color，那么：

color == next_color，花费加 0
color != next_color，花费加 1

并且走过去后 magic 一定变成 0。

第二类，下一格是无色格。

这时只有当前 magic == 0 才允许施法。你可以把下一格染成红色或黄色中的任意一种：

施法固定花费 2
若染出来的颜色和当前颜色不同，再额外花 1

所以总代价是：

2 + (color != next_color)

走过去后，新的状态 magic = 1。

所有边权都非负，因此直接在这张状态图上跑 Dijkstra 即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114#include <bits/stdc++.h>
using namespace std;

const int MAXM = 105;
const int INF = 1e9;

struct Node {
    int x, y;
    int color;   // 当前所站格子的颜色：0 红，1 黄
    int magic;   // 0 表示当前格子本来就有颜色，1 表示当前格子是用魔法临时染色的
    int dist;

    bool operator < (const Node &other) const {
        return dist > other.dist;
    }
};

int board_size, colored_cnt;
int board[MAXM][MAXM];               // -1 表示无色，其它是原始颜色
int dista[MAXM][MAXM][2][2];
bool vis[MAXM][MAXM][2][2];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool in_board(int x, int y) {
    return x >= 1 && x <= board_size && y >= 1 && y <= board_size;
}

void update_state(priority_queue<Node> &pq, int x, int y, int color, int magic, int new_dist) {
    if (new_dist >= dista[x][y][color][magic]) return;
    dista[x][y][color][magic] = new_dist;
    pq.push({x, y, color, magic, new_dist});
}

int dijkstra() {
    for (int i = 1; i <= board_size; i++) {
        for (int j = 1; j <= board_size; j++) {
            for (int c = 0; c < 2; c++) {
                for (int s = 0; s < 2; s++) {
                    dista[i][j][c][s] = INF;
                    vis[i][j][c][s] = false;
                }
            }
        }
    }

    // 起点一开始就必须有颜色，否则无法站在上面。
    if (board[1][1] == -1) return -1;

    priority_queue<Node> pq;
    int start_color = board[1][1];
    dista[1][1][start_color][0] = 0;
    pq.push({1, 1, start_color, 0, 0});

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

        int x = cur.x;
        int y = cur.y;
        int color = cur.color;
        int magic = cur.magic;

        if (vis[x][y][color][magic]) continue;
        vis[x][y][color][magic] = true;

        if (x == board_size && y == board_size) {
            return cur.dist;
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (!in_board(nx, ny)) continue;

            // 下一个格子本来就有颜色，可以直接走过去。
            if (board[nx][ny] != -1) {
                int next_color = board[nx][ny];
                int cost = (color == next_color ? 0 : 1);
                update_state(pq, nx, ny, next_color, 0, cur.dist + cost);
                continue;
            }

            // 下一个格子是无色格，只能在“当前格子不是魔法格”时施法进入。
            if (magic == 1) continue;

            for (int next_color = 0; next_color <= 1; next_color++) {
                int cost = 2; // 施法本身花 2 金币
                if (color != next_color) cost++;
                update_state(pq, nx, ny, next_color, 1, cur.dist + cost);
            }
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(board, -1, sizeof(board));

    cin >> board_size >> colored_cnt;
    for (int i = 1; i <= colored_cnt; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        board[x][y] = c;
    }

    cout << dijkstra() << '\n';
    return 0;
}

复杂度

状态数是 m^2 * 2 * 2，每个状态最多向四个方向转移一次，所以总时间复杂度是 $O(m^2 log m^2)$ ，空间复杂度是 $O(m^2)$ 。

总结

这题的关键不是“走棋盘”，而是先把影响后续决策的信息补全成状态：

当前位置
当前颜色
是否刚施法

只要这三个因素记全，它就是一题标准的状态最短路。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P3956 [NOIP 2017 普及组] 棋盘

题目背景

NOIP2017 普及组 T3

题目描述

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

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

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

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

输入格式

第一行包含两个正整数 $ m, n$，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。

接下来的 $ n $ 行，每行三个正整数 $ x, y, c $，分别表示坐标为 $(x,y)$ 的格子有颜色 $ c$。

其中 $ c=1$ 代表黄色，$ c=0$ 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标为 $(1, 1)$ ，右下角的坐标为 $( m, m)$ 。

棋盘上其余的格子都是无色。保证棋盘的左上角，也就是 $(1, 1)$ 一定是有颜色的。

输出格式

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

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

1-1

说明/提示

样例 1 说明

棋盘的颜色如下表格所示，其中空白的部分表示无色。

$\color{red}\text{红}$
$\color{yellow}\text{黄}$
	$\color{yellow}\text{黄}$	$\color{red}\text{红}$
		$\color{yellow}\text{黄}$
			$\color{red}\text{红}$

从 $(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 说明

棋盘的颜色如下表格所示，其中空白的部分表示无色。

$\color{red}\text{红}$
$\color{yellow}\text{黄}$
	$\color{yellow}\text{黄}$
		$\color{white}\text{　}$
			$\color{red}\text{红}$

从 $( 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, 0 ≤ c ≤ 2$ 。

[NOIP 2017 普及组] 棋盘

目录

题意

思路

代码

复杂度

总结

一图流解析