目标串 t=s+'*',每次操作只能选一个字符,故选择次数固定为 |t|,只需最小化滑行次数:按目标串分层做多源最短路,答案 = |t| + 最少滑行数。
OJ: roj
题目 ID: 1686
难度:提高+/省选-
标签:最短路bfsdp分层图python
创建: 2026-10-07 17:48
更新: 2026-10-07 17:48
形式化题目
给定 -、*),起点为左上角
- 选择:取出当前所在位置的字符,接到已选序列末尾;
- 滑行:选一个方向(上下左右),沿该方向逐格移动,直到落在第一个字符与出发格不同的格子上; 若这样会越出边界,则该次滑行不合法。
给定串
关键性质:每次操作最多只能选择一个字符,而目标串共
问题被拆成"选择次数固定 + 最小化滑行次数"两部分。若把"选择"当作状态推进、"滑行"当作图上的移动,
则滑行本身构成一张有向图:格子
正解
思路
最直接的想法是广搜状态 (所在格, 已选字符数):从 int 存约 100 MB,在 50×50、
注意到
= 已按顺序选出 的前 个字符、且当前停在格子 时,所用的最少滑行次数。
"选择"只发生在当前格,所以
其中
答案即
为什么这样可以丢掉
每一层的多源最短路怎么算。 源点集合
这里还有一个可用的剪枝:每层只需要"字符等于
为什么
滑行落点需要预处理:对每个格子的 4 个方向,沿该方向一直走到字符不同或出界,得到落点表,
共
一个容易踩的细节:目标串末尾那个 * 也必须被"选择"一次,它本身就是一次操作。样例中
代码
#!/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()/**
* 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;
}复杂度
预处理滑行落点
- 时间
, 最坏 、 ,实测 C++ 在顶格点( )约 0.18 s、峰值内存 8 MB; - 空间
,只有两张 的表加一个桶数组,远小于 BFS 方案的 。
Python 版为同阶算法,但在顶格点上约 7 s(C++ 的约 40 倍常数),属于语言常数导致的偏慢, 算法本身没有降级(并未退化为暴力枚举)。
总结
- 先做减法:选择次数恒为
,所以只需最小化滑行次数,目标从"最短操作序列" 变成"最短滑行总长"。 - 分层:状态
的 维可以折叠——第 层的值只在字符为 的格子上有意义, 层间转移是一次"多源单位边权最短路",第 0 层是普通 BFS。 - 单位边权用桶:初值不同的多源最短路用 Dial 桶队列代替堆;只保留每层目标格、定型即停, 是本解最关键的常数优化。
- 末尾的
*也要选择,别漏算一次操作。
关于素材:本题素材源自带数据生成脚本 data.py,说明 data/ 是自造的,题面亦可能是按
“一本通 1686” 重建而来,出题意图与官方原题可能存在偏差。经核对,素材源的 std.cpp
(以 int)在全部 10 个数据点上输出与
problem*.out 完全一致,可以信任;本题解只是把它改写成空间更省的分层最短路写法,
两者在同一组数据上输出相同(10/10)。