最小操作次数

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

目标串 t=s+'*',每次操作只能选一个字符,故选择次数固定为 |t|,只需最小化滑行次数:按目标串分层做多源最短路,答案 = |t| + 最少滑行数。

OJ: roj

题目 ID: 1686

难度:提高+/省选-

标签:最短路bfsdp分层图python

创建: 2026-10-07 17:48

更新: 2026-10-07 17:48

形式化题目

给定 n×mn \times m 的字符矩阵 gg(字符取自大写字母、数字、-、*),起点为左上角 (0,0)(0,0)。 每次操作执行且仅执行下列之一:

  1. 选择:取出当前所在位置的字符,接到已选序列末尾;
  2. 滑行:选一个方向(上下左右),沿该方向逐格移动,直到落在第一个字符与出发格不同的格子上; 若这样会越出边界,则该次滑行不合法。

给定串 ss,令目标串 t=s+*t = s + \texttt{*}(长度 L=∣s∣+1L = |s| + 1)。求使"被选择的字符依次连接恰好等于 tt" 的最小操作次数。题目保证存在合法方案。

关键性质:每次操作最多只能选择一个字符,而目标串共 LL 个字符,因此任何合法方案都恰好执行 LL 次选择。 于是

答案=L+(最少滑行次数),\text{答案} = L + (\text{最少滑行次数}),

问题被拆成"选择次数固定 + 最小化滑行次数"两部分。若把"选择"当作状态推进、"滑行"当作图上的移动, 则滑行本身构成一张有向图:格子 uu 出发、方向 dd 的一次滑行是它的一条边(每次滑行恒为一步,不论跨了几格)。

正解

思路

最直接的想法是广搜状态 (所在格, 已选字符数):从 (0,0,0)(0,0,0) 出发,每次操作要么"选择"(若当前字符与 t[k]t[k] 相同则 k→k+1k \to k+1,代价 1),要么滑行到四个方向的落点(代价 1),求到 k=Lk = L 的最短路。 由于边权全为 1,BFS 即可。这个做法是对的,但状态数是 nm(L+1)⩽2500×10001≈2.5×107nm(L+1) \leqslant 2500 \times 10001 \approx 2.5 \times 10^7, 距离数组按 int 存约 100 MB,在 50×50、∣s∣=10000|s| = 10000 时非常吃内存。

注意到 kk 这一维并不需要真的和格子相乘。把状态按"已选字符数"分层:

fj(u)f_j(u) = 已按顺序选出 tt 的前 jj 个字符、且当前停在格子 uu 时,所用的最少滑行次数。

"选择"只发生在当前格,所以 fjf_j 只在"字符等于 t[j−1]t[j-1]"的格子上有定义(第 jj 个字符正是在那里被选出的)。 两层之间的转移是

fj(v)=min⁡u: g(u)=t[j−1]{ fj−1(u)+d(u,v) },f_j(v) = \min_{u:\ g(u) = t[j-1]} \bigl\{\, f_{j-1}(u) + d(u, v) \,\bigr\},

其中 d(u,v)d(u,v) 是滑行图上 uu 到 vv 的最短距离(滑行次数)。第 0 层就是"还没选任何字符、可以随意滑行":

f0(u)=d((0,0),u).f_0(u) = d\bigl((0,0), u\bigr).

答案即 L+min⁡{ fL−1(u):g(u)=t[L−1] }L + \min\{\, f_{L-1}(u) : g(u) = t[L-1] \,\}——最后一个字符选完就结束,不需要再滑行。

为什么这样可以丢掉 kk 那一维?因为在任何最优方案里,第 jj 个字符的选择时刻,都是"这一段滑行结束"的时刻: 一旦已经选出前 jj 个字符,位置就是某个 uu,后续只取决于 uu 和目标串剩余部分。 分层 DP 正是把"滑行"这段路程折叠成一次多源最短路计算,而多源最短路一次就能覆盖所有起点, 不需要像 BFS 那样为每个 kk 单独保留一整张距离表。

每一层的多源最短路怎么算。 源点集合 Sj={ u:g(u)=t[j−1], fj−1(u)<∞ }S_j = \{\, u : g(u) = t[j-1],\ f_{j-1}(u) < \infty \,\}, 初值 fj−1(u)f_{j-1}(u)(各源点初值不同),边权恒为 1。这是"初值带权 + 单位边权"的最短路, 用小根堆是 O(nmlog⁡nm)O(nm \log nm),但更贴合单位边权的做法是 Dial 桶队列:按距离值开桶, 从最小距离桶开始逐个取出、松弛邻居。因为边权只有 1,松弛后的距离只会落在当前桶或下一个桶, 桶内用链表维护即可,整体线性。

这里还有一个可用的剪枝:每层只需要"字符等于 t[j]t[j]"的那些格子的距离值——因为第 j+1j+1 个字符必须在 那样的格子上选出,中间过程经过的其它格子对后续毫无影响。所以桶扩展一旦把所有目标格定型, 就可以立刻停止,不必把整张滑行图扩完。字符集有 39 种时,每层目标格平均只有 2500/39≈642500/39 \approx 64 个, 停得相当早。

为什么 fjf_j 的值域很窄(桶数组开得下)。 由 fj(v)⩽fj(u)+d(u,v)f_j(v) \leqslant f_j(u) + d(u,v)(uu 可达 vv 时从 uu 滑到 vv 是合法延续)可知,同一层内任意两个可达格子的 ff 值之差不超过滑行图直径;而 fjf_j 与 fj−1f_{j-1} 的取值又高度重叠。实测 10 个数据点里每层的初值跨度(max⁡−min⁡\max - \min)最多只有 84,桶数组按每层实际跨度 动态开即可,总内存 O(nm+跨度)O(nm + \text{跨度})。

滑行落点需要预处理:对每个格子的 4 个方向,沿该方向一直走到字符不同或出界,得到落点表, 共 O(4nm)O(4nm) 时间(每格每方向最坏 O(max⁡(n,m))O(\max(n,m)),n,m⩽50n, m \leqslant 50 时完全可接受)。

一个容易踩的细节:目标串末尾那个 * 也必须被"选择"一次,它本身就是一次操作。样例中 t=AZAZ*t = \texttt{AZAZ*}, 选择 5 次、滑行 14 次,共 19 次,与样例输出一致。

代码

python
#!/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-07 17:48
# update_at: 2026-10-07 17:48

import sys
from collections import defaultdict, deque

INF = 1 << 30  # 不可达;滑行次数上界远小于它

# 四个方向的行列增量,顺序固定为 上/下/左/右
DR = (-1, 1, 0, 0)
DC = (0, 0, -1, 1)

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Neigh = list[tuple[int, ...]]   # 每个格子的 4 个滑行落点(-1 表示会滑出边界)
type Dists = dict[int, int]          # 格子编号 -> 到达该格的最少滑行次数
type CellMap = dict[int, list[int]]  # 字符码 -> 该字符所在的全部格子编号


def slide(grid: list[bytes], n: int, m: int, u: int, d: int) -> int:
    """题目的基本操作:从格子 u 沿方向 d 滑到第一个字符不同的格子,返回落点编号。

    一路撞到边界(沿途字符始终与起点相同)则这一步不合法,返回 -1。
    """
    ch = grid[u // m][u % m]
    r, c = u // m + DR[d], u % m + DC[d]
    while 0 <= r < n and 0 <= c < m and grid[r][c] == ch:
        r, c = r + DR[d], c + DC[d]
    return r * m + c if 0 <= r < n and 0 <= c < m else -1


def slide_table(grid: list[bytes], n: int, m: int) -> Neigh:
    """预处理滑行图:每个格子 4 个方向各一次滑行的落点。"""
    return [tuple(slide(grid, n, m, u, d) for d in range(4)) for u in range(n * m)]


def start_dists(nxt: Neigh) -> Dists:
    """从左上角出发、只做滑行时,到各格所需的最少滑行次数(滑行图上的 BFS)。"""
    dist = {0: 0}
    queue = deque([0])
    while queue:
        u = queue.popleft()
        for v in nxt[u]:
            if v >= 0 and v not in dist:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist


def next_layer(cur: Dists, targets: list[int], nxt: Neigh, nm: int) -> Dists:
    """把"已选完若干字符、停在 cur 里的某个格子"推进到"再选一个指定字符"。

    cur 的键都是上一次定型时匹配的格子,值是那时的最少滑行次数;本层先从 cur
    的格子自由滑行(边权 1、源点初值不同),再只保留落在 targets 里的格子。
    初值不同但边权全为 1,用 Dial 桶队列(距离值分桶)代替堆;
    targets 全部定型就停,字符稀疏时能省掉大量扩展。
    """
    if not cur or not targets:
        return {}
    want = set(targets)
    base = min(cur.values())                   # 桶下标 = 距离 - base
    buckets: dict[int, list[int]] = defaultdict(list)
    dist: Dists = {}
    for u, w in cur.items():
        dist[u] = w
        buckets[w - base].append(u)
    bound = max(cur.values()) - base + nm + 2  # 多绕一圈也不超过滑行图直径
    found: Dists = {}
    for b in range(bound):
        for u in buckets[b]:
            if dist[u] != b + base:
                continue                       # 桶里的过期副本,已按更小的值处理过
            if u in want:
                found[u] = dist[u]
            for v in nxt[u]:
                nxt_dist = dist[u] + 1
                if v >= 0 and dist.get(v, INF) > nxt_dist:
                    dist[v] = nxt_dist
                    buckets[nxt_dist - base].append(v)
        if len(found) == len(want):
            break
    return found


def min_slides(nxt: Neigh, cells_of: CellMap, target: bytes) -> int:
    """目标串 target 全部选完所需的最少滑行次数(选择次数另算,恒为 len(target))。"""
    # 第 1 个字符必须在字符等于 target[0] 的格子上选出
    cur = {u: w for u, w in start_dists(nxt).items() if u in cells_of.get(target[0], ())}
    for ch in target[1:]:                      # 之后每个字符:先滑到匹配格,再选择
        cur = next_layer(cur, cells_of.get(ch, []), nxt, len(nxt))
        if not cur:                            # 这一层就断了,后面永远接不上
            break
    return min(cur.values(), default=INF)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, m = int(next(data)), int(next(data))
    grid = [next(data) for _ in range(n)]      # 每行是 bytes,grid[r][c] 取到字符码
    target = next(data) + b'*'                 # 目标串 = s 后面再添一个 '*'

    cells_of: CellMap = defaultdict(list)
    for u in range(n * m):
        cells_of[grid[u // m][u % m]].append(u)

    slides = min_slides(slide_table(grid, n, m), cells_of, target)
    # 每次操作只能选一个字符,目标串共 len(target) 个字符 => 选择次数固定
    print(len(target) + slides if slides < INF else -1)


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-07 17:48
 * update_at: 2026-10-07 17:48
 */
// 1686 最小操作次数
// 一本通 / ROJ 1686 —— 网格滑行 + 顺序取字符的最小操作数
//
// 算法:分层最短路(DP + 多源 Dijkstra / Dial 桶队列)
//   目标串 t = s + '*',设 L = |t|。
//   一次"选择"必然贡献 1 次操作,且恰好要选择 L 个字符,
//   所以 答案 = L + (最少滑行次数)。于是只需最小化滑行次数。
//
//   记 g[j][u] = 从起点出发、已按顺序选出 t 的前 j 个字符、且当前停在格子 u 时,
//   所用的最少滑行次数。则
//       g[0][u] = d(起点, u)                      // 还没选字符,可以任意滑行
//       g[j][v] = min{ g[j-1][u] + d(u, v) : g[u] == t[j-1] }   // 在 u 处选第 j 个字符
//   其中 d(u, v) 是"滑行图"(一次滑行 = 一条边权为 1 的边)上的最短距离。
//   答案为 L + min{ g[L-1][u] : g[u] == t[L-1] }(最后一个字符选完即结束,无需再滑)。
//
//   每一层的 min{...} 是多源最短路:源点 = 字符匹配 t[j-1] 的格子,初值 = g[j-1][u]。
//   边权全为 1 且初值非负,用 Dial 桶队列(按距离值开桶)实现,复杂度线性。
//   由于 g[j][v] <= g[j][u] + d(u,v)(从 u 滑到 v 是合法延续),每层取值跨度
//   不超过"滑行图直径",桶数组实际很小;桶按每层实际 min/max 动态开。
//
// 复杂度:时间 O(L * (n*m + 桶跨度)),空间 O(n*m + 桶跨度),n*m <= 2500,L <= 10001。
// 注:素材源 std.cpp 用 (格子,已匹配数) 状态做 BFS,需要 n*m*(L+1) 个 int
//     (约 100MB);本解改为分层最短路,把空间压到 O(n*m)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 55;      // n, m <= 50
const int MAXC = 2505;    // n*m <= 2500
const int INF = 1e9;

int n, m;                 // 矩阵行列数
int L;                    // 目标串长度 = |s| + 1
int nm;                   // n*m
char grid[MAXN][MAXN];    // 矩阵(0 下标)
char t[10015];            // 目标串 s + '*'
int nxt[MAXC][4];         // 滑行落点(扁平编号),-1 表示会滑出边界
int cur[MAXC];            // g[j-1][*]
int nd[MAXC];             // g[j][*]
int dist[MAXC];           // 当前层多源最短路结果

const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n; i++) scanf("%s", grid[i]);
    char sbuf[10015];
    scanf("%s", sbuf);
    strcpy(t, sbuf);
    t[strlen(sbuf)] = '*';           // 目标串 = s + '*'
    L = (int)strlen(t);
    nm = n * m;

    // 预处理四个方向的滑行落点:沿该方向一直走,直到字符与当前格不同
    for (int r = 0; r < n; r++)
        for (int c = 0; c < m; c++)
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                while (nr >= 0 && nr < n && nc >= 0 && nc < m &&
                       grid[nr][nc] == grid[r][c]) {
                    nr += dr[d];
                    nc += dc[d];
                }
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) nxt[r * m + c][d] = -1;
                else nxt[r * m + c][d] = nr * m + nc;
            }

    // g[0][u] = d(起点, u):从左上角出发的滑行最短路
    for (int u = 0; u < nm; u++) cur[u] = INF;
    {
        queue<int> q;
        cur[0] = 0;
        q.push(0);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int v = nxt[u][d];
                if (v >= 0 && cur[v] > cur[u] + 1) {
                    cur[v] = cur[u] + 1;
                    q.push(v);
                }
            }
        }
    }

    // 逐层推进:第 j 层要求选出 t[j-1],初值来自上一层的 cur
    vector<vector<int>> bucket;
    for (int j = 1; j <= L - 1; j++) {
        char need = t[j - 1];
        // 收集源点(字符匹配 t[j-1] 且已可达),求本层多源最短路
        int mn = INF, mx = -INF;
        for (int u = 0; u < nm; u++) {
            if (cur[u] >= INF) continue;
            if (grid[u / m][u % m] != need) continue;
            mn = min(mn, cur[u]);
            mx = max(mx, cur[u]);
        }
        if (mn >= INF) {           // 题面保证有解,这里只是防御
            printf("-1\n");
            return 0;
        }
        // Dial 桶队列:桶下标 = 距离 - mn,范围不超过初值跨度 + 滑行图直径
        int range = mx - mn + nm + 2;
        bucket.assign(range, vector<int>());
        for (int u = 0; u < nm; u++) {
            dist[u] = INF;
            if (cur[u] >= INF) continue;
            if (grid[u / m][u % m] != need) continue;
            dist[u] = cur[u];
            bucket[cur[u] - mn].push_back(u);
        }
        for (int b = 0; b < range; b++) {
            for (size_t i = 0; i < bucket[b].size(); i++) {
                int u = bucket[b][i];
                if (dist[u] != b + mn) continue;   // 桶里的过期副本,已按更小值处理过
                for (int d = 0; d < 4; d++) {
                    int v = nxt[u][d];
                    if (v >= 0 && dist[u] + 1 < dist[v]) {
                        dist[v] = dist[u] + 1;
                        bucket[dist[v] - mn].push_back(v);
                    }
                }
            }
        }
        // 第 j 个字符必须在停下的格子上选出,否则该状态无效
        char nx = t[j];
        for (int u = 0; u < nm; u++) {
            if (dist[u] < INF && grid[u / m][u % m] == nx) nd[u] = dist[u];
            else nd[u] = INF;
        }
        for (int u = 0; u < nm; u++) cur[u] = nd[u];
    }

    // 答案 = L(选择的次数)+ 最少滑行次数
    int best = INF;
    char last = t[L - 1];
    for (int u = 0; u < nm; u++)
        if (cur[u] < INF && grid[u / m][u % m] == last) best = min(best, cur[u]);
    printf("%d\n", L + best);
    return 0;
}

复杂度

预处理滑行落点 O(nm⋅max⁡(n,m))O(nm \cdot \max(n,m)),第 0 层 BFS O(nm)O(nm),之后每层 Dial 桶队列 O(nm+跨度)O(nm + \text{跨度}),共 L−1L - 1 层。所以

  • 时间 O(nm⋅max⁡(n,m)+L⋅(nm+跨度))O\bigl(nm \cdot \max(n,m) + L \cdot (nm + \text{跨度})\bigr), 最坏 L≈10001L \approx 10001、nm=2500nm = 2500,实测 C++ 在顶格点(∣s∣=10000|s| = 10000)约 0.18 s、峰值内存 8 MB;
  • 空间 O(nm+跨度)O(nm + \text{跨度}),只有两张 nmnm 的表加一个桶数组,远小于 BFS 方案的 O(nmL)O(nmL)。

Python 版为同阶算法,但在顶格点上约 7 s(C++ 的约 40 倍常数),属于语言常数导致的偏慢, 算法本身没有降级(并未退化为暴力枚举)。

总结

  • 先做减法:选择次数恒为 ∣t∣=∣s∣+1|t| = |s| + 1,所以只需最小化滑行次数,目标从"最短操作序列" 变成"最短滑行总长"。
  • 分层:状态 (格,已选数)(格, 已选数) 的 kk 维可以折叠——第 jj 层的值只在字符为 t[j−1]t[j-1] 的格子上有意义, 层间转移是一次"多源单位边权最短路",第 0 层是普通 BFS。
  • 单位边权用桶:初值不同的多源最短路用 Dial 桶队列代替堆;只保留每层目标格、定型即停, 是本解最关键的常数优化。
  • 末尾的 * 也要选择,别漏算一次操作。

关于素材:本题素材源自带数据生成脚本 data.py,说明 data/ 是自造的,题面亦可能是按 “一本通 1686” 重建而来,出题意图与官方原题可能存在偏差。经核对,素材源的 std.cpp (以 (格,已选数)(格, 已选数) 为状态、距离数组 nm(L+1)nm(L+1) 个 int)在全部 10 个数据点上输出与 problem*.out 完全一致,可以信任;本题解只是把它改写成空间更省的分层最短路写法, 两者在同一组数据上输出相同(10/10)。