「一本通 1.4 例 1」电路维修

形式化题目

棋盘上有 $N$ 行 $M$ 列的正方形元件，元件 $(r,c)$ 占据边框 $[r,r+1] \times [c,c+1]$ 。每个元件内部有一段连接一对对角顶点的导线：

\ 连通左上顶点 $(r,c)$ 与右下顶点 $(r+1,c+1)$ ；
/ 连通右上顶点 $(r,c+1)$ 与左下顶点 $(r+1,c)$ 。

每个元件可以旋转 $90°$ （两个方向都可以），每旋转一次记 1 次操作。

把电路板的顶点看成 $(N+1) \times (M+1)$ 个格点，电源在格点 $(0,0)$ ，灯泡在格点 $(N,M)$ 。求最少的旋转次数，使得 $(0,0)$ 与 $(N,M)$ 之间存在一条由导线首尾相接构成的通路；若不存在任何旋转方案能连通，则报告无解。

正解

思路

从「转元件」到「选边」

连通性发生在格点上：两块相邻元件的导线要在它们共享的那个格点处相遇，通路才能延续。所以图的点应该是格点，而不是元件。

抓住这一点，注意一个事实：任意一对对角格点，由唯一一块元件决定它们能否直连。例如格点 $(r,c)$ 与 $(r+1,c+1)$ 这一对，只由元件 $(r,c)$ 决定：

元件是 \ → 它正好连着这一对，不用旋转，代价 0；
元件是 / → 它连的是另一对，要让这一对导通必须转一次，代价 1。

同样的，格点 $(r,c+1)$ 与 $(r+1,c)$ 这一对也由同一块元件决定，但刚好相反： / 时代价 0，\ 时代价 1。

于是每块元件相当于给「某一条对角线」上的一条边赋了权 0 或 1：

格点对	由哪块元件决定	代价 0 的朝向	代价 1 的朝向
$(r,c) \to (r+1,c+1)$	元件 $(r,c)$	`\`	`/`
$(r+1,c) \to (r,c+1)$	元件 $(r,c)$	`/`	`\`

这一步就是整道题的枢纽：原本「选一个旋转方案」是 $2^{NM}$ 的组合问题，现在变成了「在这个 0/1 权图上从 $(0,0)$ 走到 $(N,M)$ 」的最短路问题。

为什么每块元件最多只贡献一次旋转

有人会担心一条路径反复经过同一块元件的两个方向，把一次旋转算成两次。不会发生：一块元件在同一时刻只能提供一条对角线（朝向二选一）。路径一旦用了某个方向，用到的就是该元件当时的朝向；另一条对角线在该元件旋转后就不存在了。一条最短路不会重复走同一条边，所以每块元件的旋转被统计且仅被统计一次。

为什么用 0-1 BFS 而不是普通 BFS 或 Dijkstra

普通 BFS 要求所有边等权，这里边权有 0 有 1，直接用会错；
Dijkstra 配堆能做，但多了 $O(\log V)$ 的常数；
0-1 BFS 正合适：维护一个双端队列，队列里始终按 dist 非递减排列——
- 走权 0 的边：新点距离不变，塞进队头；
- 走权 1 的边：新点距离 +1，塞进队尾。
这样每个格点第一次被弹出时，它的距离就已经是最终最短路，可以直接返回。总复杂度 $O(V+E) = O(NM)$ 。

算法流程

dist[r][c] = -1 表示未访问，dist[0][0] = 0，队列放 $(0,0)$ 。
弹出队头 $(r,c)$ ：如果它就是 $(N,M)$ ，直接返回 dist[r][c]。
对四个对角方向 $(dr,dc) \in \{(-1,-1),(1,1),(-1,1),(1,-1)\}$ ：
- 目标格点 $(r+dr,c+dc)$ 越界就跳过；
- 跨过的那块元件位于行列各取较小的位置，即 $(\min(r,r+dr),\ \min(c,c+dc))$ ；
- 权值 $w = [\text{元件朝向} \neq \text{该方向所需朝向}]$ ；
- 若 dist[r][c] + w 更优就更新，并按 $w$ 是 0 还是 1 决定塞队头还是队尾。
队列空了还没到 $(N,M)$ ，说明无解。

「行列各取较小值」这个写法值得留意：往左上走时元件在当前格点的上一行，往右下走时元件在当前行，统一写成取 min 就没有分支，也不会越界或取错格子。

无解怎么判

无解的来源有两类，但不需要分别特判：

奇偶性：对角移动让 $r+c$ 的奇偶性不变（改变量是 $0$ 或 $\pm 2$ ），起点 $r+c$ 是偶数，所以 $N+M$ 为奇数时终点必然不可达；
真实阻隔： $N+M$ 为偶数时也可能因为朝向分布而不可达，例如 $1 \times 2$ 的 \\。

两者都表现为「队列空掉后 dist[N][M] 仍然是 -1」，统一从同一个出口输出 NO SOLUTION。

样例推演

样例是 $3 \times 5$ ：

text

1
2
3\\/\\
\\///
/\\\\

下面是 0-1 BFS 求出的格点距离表，行列分别对应格点坐标 $r = 0\dots3$ 、 $c = 0\dots5$ ，单元格里的数字是从电源 $(0,0)$ 到该格点的最少旋转次数，-1 表示不可达：

$r \backslash c$	0	1	2	3	4	5
0	0	-1	1	-1	1	-1
1	-1	0	-1	0	-1	1
2	1	-1	0	-1	1	-1
3	-1	1	-1	0	-1	1

可以看出两点。第一，所有可达格点都满足 $r+c$ 为偶数，-1 恰好填满另一半，这正是奇偶性观察的直接体现。第二，沿主对角线 $(0,0) \to (1,1) \to (2,2) \to (3,3)$ 一路都是 0，因为这三块元件本来就是 \；从 $(3,3)$ 绕到 $(2,4)$ 时要跨过元件 $(2,3)$ ，往右上需要 / 而实际是 \，于是花了唯一的一次旋转，之后 $(2,4) \to (3,5)$ 又是 0，最终答案 1。

这恰好对应题面那句「把右边数第二列的任意一块元件转 $90°$ 」。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 11:11
# update_at: 2026-09-30 11:32

import sys
from collections import deque

BACKSLASH = ord('\\')  # 反斜杠元件：导线连通「左上—右下」一对顶点
SLASH = ord('/')       # 斜杠元件：导线连通「右上—左下」一对顶点

# 从格点斜着跨过一块元件到达对角格点，需要该元件是哪种方向。
# 每项 = (行偏移, 列偏移, 直通所需的方向)；跨过的元件总是位于 (min(行), min(列))。
STEPS = (
    (-1, -1, BACKSLASH),  # 左上：走元件的「右下」半条线
    (1, 1, BACKSLASH),    # 右下：走元件的「左上」半条线
    (-1, 1, SLASH),       # 右上：走元件的「左下」半条线
    (1, -1, SLASH),       # 左下：走元件的「右上」半条线
)


def light_up(grid: list[bytes], n: int, m: int) -> int:
    """返回点亮灯泡所需的最少旋转次数，无解返回 -1。

    图上的点 = 电路板的 (N+1)×(M+1) 个格点，边 = 斜着跨过一块元件到对角格点。
    若元件方向正好能穿过，边权 0；否则要把它转 90°，边权 1。于是问题变成 0-1 BFS。
    """
    dist = [[-1] * (m + 1) for _ in range(n + 1)]  # -1 表示尚未到达该格点
    dist[0][0] = 0
    queue = deque([(0, 0)])

    while queue:
        r, c = queue.popleft()
        d = dist[r][c]
        if (r, c) == (n, m):  # 0-1 BFS 出队即最短路，第一次弹出终点就是答案
            return d
        for dr, dc, need in STEPS:
            nr, nc = r + dr, c + dc
            if not (0 <= nr <= n and 0 <= nc <= m):
                continue  # 目标格点越界
            # 跨过的元件就是两个格点围成的那个格子：行列各取小的那个
            cost = d + (grid[min(r, nr)][min(c, nc)] != need)  # 方向不符要转一次
            if dist[nr][nc] < 0 or cost < dist[nr][nc]:
                dist[nr][nc] = cost
                # 边权 0 走队头、边权 1 走队尾，队列始终按 dist 非递减排列
                (queue.appendleft if cost == d else queue.append)((nr, nc))

    return -1  # 队列空了还没弹出终点，说明电源与灯泡不连通


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    m = int(next(data))
    grid = [next(data) for _ in range(n)]  # 每行一个 bytes，逐字节比较方向更快
    ans = light_up(grid, n, m)
    print('NO SOLUTION' if ans < 0 else ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 02:25
 * update_at: 2026-10-05 02:25
 */

#include <cstdio>
#include <deque>
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

const int MAXN = 505; // N, M <= 500，格点数为 (N+1)*(M+1)

int n; // 元件行数
int m; // 元件列数

string grid[MAXN]; // grid[r][c] 是元件 (r,c) 的导线方向，'\\' 或 '/'

int dist[MAXN][MAXN]; // dist[r][c] = 从电源格点 (0,0) 到格点 (r,c) 的最少旋转次数，-1 表示不可达

// 从当前格点斜着跨过一块元件走到对角格点。
// 每项 = (行偏移, 列偏移, 直通所需方向)：跨过的元件总是位于 (min(行), min(列))。
const int STEP_CNT = 4;
const int step_r[STEP_CNT] = {-1, 1, -1, 1};
const int step_c[STEP_CNT] = {-1, 1, 1, -1};
const char step_need[STEP_CNT] = {'\\', '\\', '/', '/'}; // 方向相符则不用旋转，边权 0

// 0-1 BFS：图上的点是 (N+1)*(M+1) 个格点，边是斜跨一块元件。
// 边权 0 的邻点塞队头，边权 1 的塞队尾，保证出队时距离已是最短路。
ll zero_one_bfs() {
    for (int r = 0; r <= n; r++) {
        for (int c = 0; c <= m; c++) {
            dist[r][c] = -1;
        }
    }
    deque<pair<int, int> > dq; // 队列中每个元素是一个格点 (r,c)
    dist[0][0] = 0;
    dq.push_back(make_pair(0, 0));

    while (!dq.empty()) {
        int r = dq.front().first;
        int c = dq.front().second;
        dq.pop_front();
        int d = dist[r][c];
        if (r == n && c == m) {
            return d; // 第一次弹出终点即为答案
        }
        for (int k = 0; k < STEP_CNT; k++) {
            int nr = r + step_r[k];
            int nc = c + step_c[k];
            if (nr < 0 || nr > n || nc < 0 || nc > m) {
                continue; // 目标格点越界
            }
            // 跨过的元件就是两个格点围成的那一格：行列各取较小的那个
            int pr = r < nr ? r : nr;
            int pc = c < nc ? c : nc;
            int w = 0; // 元件方向正好能穿过时不用旋转
            if (grid[pr][pc] != step_need[k]) {
                w = 1; // 方向不符，要转 90°，代价 1
            }
            int nd = d + w;
            if (dist[nr][nc] == -1 || nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                if (w == 0) {
                    dq.push_front(make_pair(nr, nc));
                } else {
                    dq.push_back(make_pair(nr, nc));
                }
            }
        }
    }
    return -1; // 队列空掉仍未到终点，说明无法连通
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int r = 0; r < n; r++) {
        cin >> grid[r];
    }
    ll ans = zero_one_bfs();
    if (ans < 0) {
        cout << "NO SOLUTION" << '\n';
    } else {
        cout << ans << '\n';
    }
    return 0;
}

复杂度

时间： $O(NM)$ 。格点数为 $(N+1)(M+1)$ ，每个格点最多入队常数次。
空间： $O(NM)$ 。一张 $(N+1)\times(M+1)$ 的距离表和双端队列。

在 $N,M \leqslant 500$ 的最大数据上， $V \approx 2.5\times 10^5$ 、 $E \approx 10^6$ ，实测最慢测试点 0.111 s、峰值内存 22.0 MB，明显低于 1000 ms / 128 MB 的限制。

总结

本题的全部难度在建模，不在算法：

连通性属于格点，不属于元件——所以要建 $(N+1)\times(M+1)$ 个点的图；
每对对角格点由唯一一块元件决定——于是每块元件退化成一条边，权值就是「要不要转这一下」，只有 0 和 1；
0/1 权图的最短路用 0-1 BFS——双端队列保证出队即定稿， $O(NM)$ 收工。

一旦完成第 2 步，问题就从 $2^{NM}$ 的组合搜索塌缩成一次最短路，这是「把操作代价搬到边上」这一类建模的典型手法。