形式化题目

给定一个 $R$ 行 $C$ 列的网格。每个格子 $(i,j)$ 里有一条可以旋转的线段，它连接该格子两条对角线中的一条：

• 主对角线连接左上角格点 $(i,j)$ 与右下角格点 $(i+1,j+1)$；
• 副对角线连接右上角格点 $(i,j+1)$ 与左下角格点 $(i+1,j)$。

把一条线段旋转一下，它就从一条对角线换到另一条对角线，代价为 $1$；不旋转则代价为 $0$。

要求只沿着网格中的斜线段行走（水平、竖直方向都不能走），用最少的旋转次数把左上角格点 $(0,0)$ 与右下角格点 $(R,C)$ 连通；若无论怎么旋转都连不通，则报告不可达。

正解

思路

朴素做法走不通在哪。 最直接的思路是枚举"旋转哪些格子"：每个格子旋转或不旋转，一共 $2^{RC}$ 种选择，每次还要做一次连通性检查，$R=C=500$ 时是天文数字。

瓶颈在于决策对象选错了。目标函数是"被旋转的格子数"，而一个格子要不要旋转，其实只取决于我们走过的路径有没有用到它。所以换一个决策对象——先决定"走哪条路"，再数这条路上有多少格子方向不对：

一条路径的代价 = 这条路径穿过的格子中，"方向和穿越方式不符"的个数。

这个量是沿路径逐段累加的。凡是代价可以逐段累加的问题，都可以用最短路求最小值。于是题目从"指数级枚举"变成了"求一条最小代价路径"。

把网格翻译成图。 把每个格点 $(i,j)$（$0\leqslant i\leqslant R,\ 0\leqslant j\leqslant C$）当成图的一个节点；两个格点之间只要沿斜线相邻，就有一条边。从格点 $u=(i,j)$ 出发只有四个斜向邻居，而每条边都恰好穿过唯一一个格子：

穿过的格子的方向本来就对，这条边不用花任何代价；需要转过来，这条边就花 $1$ 次旋转。所以每条边的权只可能是 $0$ 或 $1$，绝不会有别的取值。答案就是从 $(0,0)$ 到 $(R,C)$ 的最短路长度。

用样例确认模型。 样例的网格如下。（ROJ 题面里的样例在渲染时丢了一层转义，显示成每行 3/4/3 个字符，与 $C=5$ 矛盾；下面是转义还原后、每行 5 个字符的正确样例。）

按上面的规则跑一遍最短路，把每个格子的方向与它周围格点的距离叠在一起看（. 表示走不到）：

1
2
3
4
5格点距离             格子方向
 0   .   1   .   1   .        \  \  /  \  \
 .   0   .   0   .   1        \  \  /  /  /
 1   .   0   .   1   .        /  \  \  \  \
 .   1   .   0   .   1

终点 $(3,5)$ 的值是 $1$，与输出样例一致。只有 $i+j$ 为偶数的格点有值，这是后面要用的奇偶性。最优路径穿过格子 $(0,0),(1,1),(1,2),(1,3),(2,4)$，其中只有 $(1,3)$ 原来是 /、需要转成 \，恰好 $1$ 次旋转。

边权只有 $0$ 和 $1$，选什么最短路算法。 四种做法的对比：

普通 BFS 错在哪：它成立的前提是“所有边权相等”，靠这个前提才能保证“先入队的点距离一定更小”。这里存在权为 $0$ 的边，如果还按普通规则把 $0$ 权边的点排到队尾，就会出现“距离 $1$ 的点排在距离 $0$ 的点前面”，后继点被记成更大的距离，最终答案偏大。这不是理论担心：在 $4000$ 组随机小网格里有 $2090$ 组会偏大（例如 $2\times4$ 的 /\/\、\\\/，正确答案是 $3$，普通 BFS 会得到 $4$）。

而 Dijkstra 之所以正确，靠的是"优先队列每次弹出当前最小的点"。在这张图里，当前层的距离是 $d$，下一层是 $d+1$，优先队列中同时只会存在这两种值。既然只有两种值，就不需要堆，只要两个"桶"：

• 松弛后距离仍是 $d$ 的点（走的是 $0$ 权边），放进队头——它和当前层同级，应该紧接着处理；
• 松弛后距离变成 $d+1$ 的点（走的是 $1$ 权边），放进队尾——它属于下一层。

用一个双端队列（deque）就能实现这两个桶：appendleft 对应队头，append 对应队尾。这样队列从头到尾的距离始终单调不降，第一次弹出终点的距离就是答案。这就是 0-1 BFS，本质是"两个桶代替优先队列"的 Dijkstra。

落到代码上：上面那张四向表就是模块级常量 NEIGHBOURS 的每一项 (di, dj, ci, cj, want)；边权写成 nd = d + (rows[i + ci][j + cj] != want)——穿越格子的方向与 want 不符时布尔值为 True，可直接当 $1$ 相加；W = C + 1 把格点编号成 u = i * W + j；最后 if nd > d: append(v) else: appendleft(v) 就是上面说的"$1$ 权进队尾、$0$ 权进队头"。

为什么可以放心地把"边权之和"当成"旋转次数"。 还差最后一步：最短路算的是"路径上方向不符的边有多少条"，而题目要求的是"要旋转多少个格子"，这两者什么时候相等？

答案是永远相等。每个斜向移动都会让 $i+j$ 变化 $\pm 2$ 或 $0$，奇偶性不变，所以整条路径上的格点都满足 $i+j$ 为偶数。再看一个格子的两条对角线：主对角线两端点是 $(i,j)$、$(i+1,j+1)$，$i+j$ 的奇偶性相同；副对角线两端点是 $(i+1,j)$、$(i,j+1)$，$i+j$ 的奇偶性也相同，但与主对角线相反。两条对角线分属不同奇偶类。既然路径只在偶数类格点上走，每个格子在偶数类里就恰好只有一条对角线可用（格子 $i+j$ 为偶数时是主对角线 \，为奇数时是副对角线 /）——同一个格子绝不会既被当成 $0$ 权边又被当成 $1$ 权边，也就不会被重复计数。

顺带得到一个推论：如果 $R+C$ 是奇数，终点和起点的奇偶类不同，无论怎么旋转都连不通，直接输出 NO SOLUTION。代码里不必特判，BFS 自然会算出"不可达"。

代码

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
64
65
66
67
68
69
70
71
72#!/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-10-01 14:23
# update_at: 2026-10-01 14:23

import sys
from collections import deque

SLASH, BACKSLASH = 47, 92  # 字节 b'/' 与 b'\\' 的 ASCII 码，直接和网格字节比
INF = 1 << 30              # 到不了的距离，比 250000 步的上界大得多

# 一条斜边可以看成"从当前格点走到对角的那个格点"：
# (格点位移 di, dj；被穿过的格子相对当前格点的位移 ci, cj；该格原本应有的方向)。
NEIGHBOURS = (
    (1, 1, 0, 0, BACKSLASH),      # 右下：穿过格子 (i, j)，本来就得是 '\'
    (1, -1, 0, -1, SLASH),        # 左下：穿过格子 (i, j-1)，本来就得是 '/'
    (-1, 1, -1, 0, SLASH),        # 右上：穿过格子 (i-1, j)，本来就得是 '/'
    (-1, -1, -1, -1, BACKSLASH),  # 左上：穿过格子 (i-1, j-1)，本来就得是 '\'
)


def min_rotations(rows: list[bytes], R: int, C: int) -> int:
    """从左上角格点走到右下角格点所需的最少旋转次数，不可达返回 INF。

    把每个格点当节点：方向已经对上的斜边权为 0，需要转一次的权为 1，
    于是问题变成 0-1 图上的最短路，用双端队列 BFS 在 O(RC) 内求出。
    """
    W = C + 1                                # 格点按 u = i * W + j 一维编号
    dist = [INF] * ((R + 1) * W)
    dist[0] = 0
    target = R * W + C
    queue = deque([0])

    while queue:
        u = queue.popleft()
        if u == target:
            break                            # 出队时距离已定型，后面不可能更小
        d = dist[u]
        i, j = divmod(u, W)
        for di, dj, ci, cj, want in NEIGHBOURS:
            ni, nj = i + di, j + dj
            if 0 <= ni <= R and 0 <= nj <= C:
                nd = d + (rows[i + ci][j + cj] != want)  # 方向不对就要转这个格子
                v = u + di * W + dj
                if nd < dist[v]:
                    dist[v] = nd
                    if nd > d:
                        queue.append(v)
                    else:
                        queue.appendleft(v)  # 0 权边走队头，双端队列才保持距离有序

    return dist[target]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    T = int(next(data))

    for _ in range(T):
        R, C = int(next(data)), int(next(data))
        rows = [next(data) for _ in range(R)]
        answer = min_rotations(rows, R, C)
        out.append("NO SOLUTION" if answer >= INF else str(answer))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 17:13
 * update_at: 2026-10-06 17:13
 */

#include <iostream>
#include <deque>
#include <utility>
using namespace std;

typedef long long ll;

const int MAXR = 505;
const int MAXC = 505;
const int INF = 0x3f3f3f3f;

// 四个斜向邻居：(di, dj, 穿越格子相对当前格点的偏移 ci, cj, 该格需要的方向)
// 方向用字符存储，与读入的 grid[i][j] 直接比较
const int DIR[4][5] = {
    { 1,  1,  0,  0, '\\'}, // 右下，穿过格子 (i, j)，需要 '\'
    { 1, -1,  0, -1,  '/'}, // 左下，穿过格子 (i, j-1)，需要 '/'
    {-1,  1, -1,  0,  '/'}, // 右上，穿过格子 (i-1, j)，需要 '/'
    {-1, -1, -1, -1, '\\'}, // 左上，穿过格子 (i-1, j-1)，需要 '\'
};

char grid[MAXR][MAXC];   // 格子方向，下标从 0 开始
int dist[MAXR][MAXC];    // 格点 (i,j) 的最短距离，格点范围 0..R, 0..C

deque<pair<int, int>> q; // 0-1 BFS 双端队列，存格点坐标

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

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int R, C;
        cin >> R >> C;
        for (int i = 0; i < R; ++i) {
            cin >> grid[i];
        }

        // 初始化距离数组，只清实际用到的范围
        for (int i = 0; i <= R; ++i) {
            for (int j = 0; j <= C; ++j) {
                dist[i][j] = INF;
            }
        }
        while (!q.empty()) q.pop_back();

        dist[0][0] = 0;
        q.push_back(make_pair(0, 0));

        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop_front();
            int i = cur.first;
            int j = cur.second;
            int d = dist[i][j];
            if (i == R && j == C) break; // 终点出队时距离已定型

            for (int k = 0; k < 4; ++k) {
                int ni = i + DIR[k][0];
                int nj = j + DIR[k][1];
                if (ni < 0 || ni > R || nj < 0 || nj > C) continue;
                int ci = i + DIR[k][2];
                int cj = j + DIR[k][3];
                int want = DIR[k][4];
                int w = (grid[ci][cj] != want) ? 1 : 0; // 方向不对代价为 1
                int nd = d + w;
                if (nd < dist[ni][nj]) {
                    dist[ni][nj] = nd;
                    if (w == 0) {
                        q.push_front(make_pair(ni, nj)); // 0 权边放队头
                    } else {
                        q.push_back(make_pair(ni, nj));  // 1 权边放队尾
                    }
                }
            }
        }

        if (dist[R][C] == INF) {
            cout << "NO SOLUTION\n";
        } else {
            cout << dist[R][C] << "\n";
        }
    }
    return 0;
}

复杂度

• 时间复杂度：$O(RC)$。每个格点最多入队常数次（实测在全部公开数据、$30000$ 组随机小网格、以及 $12$ 格以内的穷举中，最多只入队 $2$ 次），出队时检查 $4$ 个邻居，每条边最多松弛一次；共 $T$ 组，总计 $O(T\cdot RC)$。最大规模 $T=5$、$R=C=500$ 时约 $1.25\times10^6$ 个格点、$2.5\times10^6$ 次边检查，本地实测最慢 $0.27$ s。
• 空间复杂度：$O(RC)$。一张长度 $(R+1)(C+1)\leqslant 251001$ 的一维距离数组、一个双端队列和 $R$ 行输入，实测峰值约 $22$ MB，低于 $128$ MB 的限制。

总结

• 决策对象从"旋转哪些格子"换成"走哪条路径"之后，代价变成可加量，题目立刻落进最短路框架。
• 每条边要么不花代价（格子方向已对），要么花 $1$（要把格子转过来），边权只有 $0$ 和 $1$。
• 边权含 $0$ 时普通 BFS 会给出偏大的答案；改用 0-1 BFS：$0$ 权边推队头、$1$ 权边推队尾，用双端队列替代优先队列，$O(RC)$ 正确求解。
• 由于每次斜向移动不改变 $i+j$ 的奇偶性，路径上同一格子不会被两条不同的对角线重复使用，"边权之和"与"需要旋转的格子数"恰好相等；推论是 $R+C$ 为奇数时必然 NO SOLUTION。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6
7
8R×C 网格，每格一条可旋转的对角线
`- 把格点当节点、斜线段当边
   |- 格子方向已对 -> 边权 0
   `- 格子需要旋转 -> 边权 1
      `- 边权只取 {0, 1}
         |- 普通 BFS：0 权边破坏层序 -> 答案偏大
         `- 双端队列 BFS：0 权进队头、1 权进队尾
            `- O(RC) 得到 (0,0) 到 (R,C) 的最少旋转次数

先看第一层：网格结构和图结构之间是"每条斜边恰好属于一个格子"的一一对应。再顺着分支往下看，两个叶子分别否定了普通 BFS、给出了 0-1 BFS；最后一行是复杂度结论。图中只保留正文已经论证过的关系，样例的具体数值推演见 ### 思路 中的两张表。