把单词的每次出现看成一条最多拐一次 90° 弯的路径，枚举起点与初始方向，顺着路径逐格匹配计数。
OJ: roj
题目 ID: 20017
难度:普及-
标签:网格枚举搜索
日期: 2026-08-28 22:10
形式化题目
给定 R × C 个大写字母网格（R, C ≤ 100）和由互不相同字母组成的单词 W（长度 ≥ 2），统计 W 在网格中的出现次数。
一次出现 = 一条恰好按顺序覆盖 W 全部字母的格子序列：
- 直线：所有字母在同一条水平 / 竖直 / 主对角 / 副对角线上，可正向也可反向读取；
- L 形：先沿一条直线放置前 k 个字母（k ≥ 2），再沿与之垂直的直线放置剩余字母，形成一次 90° 直角拐弯。
同一格子的同一种摆放只计一次。
思路
一句话本质：把单词的每次出现看成一条"最多拐一次 90° 弯"的路径；只要枚举起点和初始方向，路径的剩余形状就完全确定，顺着路径逐格匹配即可计数。
问题？ 为什么一次出现可以被当成一条"路径"来看？
直线和 L 形本质上都是同一件事：一个起点、一条初始方向，先沿直线走若干格，最多在某处转一次 90° 弯再走完剩下的字母。直线就是"不转弯"的特例，L 形就是"在某两个字母之间转了弯"。于是问题变成：网格里有多少条格子序列恰好按顺序覆盖 W 的字母。
问题？ 要枚举什么才能不重不漏地找到所有出现？
任何一次出现，放 W[0] 的起点格子是唯一的，从起点到第二个字母的方向也一定是 8 个方向之一。所以枚举"起点（内容为 W[0] 的格子）+ 初始方向"就覆盖了所有出现，且不同的起点对应不同的出现，天然不重复。正向 / 反向读取也不用特殊处理：反向读就是从那头的 W[0] 格子开始正向走，同样落在枚举范围内。
问题？ 拐弯到底发生在哪一步？
把路径分成两段：第一段沿方向 d1 放 k 个字母，第二段沿垂直方向 d2 放剩余 L-k 个字母。这里有一个官方数据验证过的细节：第一段至少要有 2 个字母，即拐点不能是起点。若允许第一段只有 1 个字母，官方 10 组数据中的 6 组答案都会偏大（例如第 1 组 6 变成 18，第 7 组 20 变成 30），所以"一部分沿一条直线"的隐含意思是这段至少有两个字母。
看一个同时出现两种形状的小例子，单词 ABCDE：
1 2 3 4 5
1 A B C D E
2 X X D X X
3 X X E X X- 直线：A(1,1) → B(1,2) → C(1,3) → D(1,4) → E(1,5)；
- L 形：A(1,1) → B(1,2) → C(1,3)，在 C 处拐 90° 弯，D(2,3) → E(3,3)。
这张图同时展示两种出现：直线和 L 形共用一个起点，差别只在 C 之后是继续直走还是转弯。注意 L 形的拐点 C 不是起点——从 A 到 B 已经走了一格，第一段有 2 个以上字母后才允许转弯，这正是"第一段至少 2 个字母"的含义。
问题？ 最直接的写法是什么？
把摆放方式完整枚举出来：对每个起点、每个初始方向 d1、每个拐点位置 k（k = L 是直线，2 ≤ k ≤ L-1 是 L 形）、每个垂直方向 d2，从头到尾逐字符检查整条路径。这就是下面的朴素解：
/**
* 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-08-28 21:28
* update_at: 2026-08-28 21:28
*/
// brute.cpp：小数据暴力解，枚举所有“摆放方式”并逐字符检查。
// 摆放方式 = (起点, 第一段方向, 拐点位置 k, 第二段方向)，
// 直线看成拐点不存在，L 形看成第一段 k 个字母后转 90 度。
// 复杂度较高（O(R*C*8*L*L)），只适合小数据验证与对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXRC = 105;
string w; // 要找的单词 W
int R, C; // 网格行数、列数
char g[MAXRC][MAXRC]; // 网格
int ans = 0;
// 8 个方向：0 上，1 右上，2 右，3 右下，4 下，5 左下，6 左，7 左上
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// 从 (x,y) 出发，第一段沿方向 d1 放 len1 个字母，第二段沿方向 d2 放剩余字母，
// 逐字符检查整条路径上的字母是否恰好等于 w。
bool check_path(int x, int y, int d1, int len1, int d2) {
int L = (int)w.size();
// 第一段：第 0..len1-1 个字母
for (int t = 0; t < len1; t++) {
int nx = x + dx[d1] * t;
int ny = y + dy[d1] * t;
if (nx < 0 || nx >= R || ny < 0 || ny >= C || g[nx][ny] != w[t]) {
return false;
}
}
// 第二段：拐点在 (x + dx[d1]*(len1-1), y + dy[d1]*(len1-1))，之后沿 d2 走
for (int t = len1; t < L; t++) {
int nx = x + dx[d1] * (len1 - 1) + dx[d2] * (t - len1 + 1);
int ny = y + dy[d1] * (len1 - 1) + dy[d2] * (t - len1 + 1);
if (nx < 0 || nx >= R || ny < 0 || ny >= C || g[nx][ny] != w[t]) {
return false;
}
}
return true;
}
void solve() {
int L = (int)w.size();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (g[i][j] != w[0]) {
continue;
}
for (int d1 = 0; d1 < 8; d1++) {
// 直线：整条路径沿 d1，相当于第一段长度为 L、没有第二段
if (check_path(i, j, d1, L, d1)) {
ans++;
}
// L 形：第一段 k 个字母（2 <= k <= L-1），然后向两个垂直方向拐
for (int k = 2; k <= L - 1; k++) {
for (int d2 = 2; d2 <= 6; d2 += 4) { // 两个垂直方向
int nd2 = (d1 + d2) % 8;
if (check_path(i, j, d1, k, nd2)) {
ans++;
}
}
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> w >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> g[i][j];
}
}
solve();
cout << ans << '\n';
return 0;
}问题？ 朴素解慢在哪里？
对同一个 (起点, 方向)，换一个拐点 k 就要把前面 k 个字母重新检查一遍：k=2 检查前 2 个，k=3 又从头检查前 3 个……同一段前缀被反复比对，单个起点要花 O(L²) 次字符比较。本题数据小（R,C ≤ 100）能跑，但重复是多余的。
问题？ 怎样消除重复检查？
边走边匹配：从起点沿一个方向逐格推进，每走一步只检查当前这一个格子；"转弯"作为至多一次的选择并入游走过程，用 DFS 记录状态 (已匹配字母数, 当前位置, 当前方向, 是否已转弯)。这样每个前缀只被检查一次。
问题？ DFS 为什么不会重复计数？
一次出现就是一条确定的格子序列；DFS 从起点出发生成的游走记录恰好是这条序列本身，一条序列只会被生成一次。更形式化地说：格子序列唯一决定起点（放 W[0] 的格子）、第一段方向（第 1→2 格的方向）、拐点位置（方向第一次改变处）和第二段方向，所以"每格每方向游走一次"不重不漏。turned 标记保证整条路径至多拐一次弯。
代码
/**
* 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-08-28 21:28
* update_at: 2026-08-28 21:28
*/
// main.cpp：B. Treasure（藏宝图）最终解。
// 从每个格子出发，沿 8 个方向搜索单词；用一个标记记录是否已经转过一次 90 度弯。
// 每个格子作为起点、每个方向作为初始方向，天然保证同一种摆放只被计数一次。
#include <bits/stdc++.h>
using namespace std;
const int MAXRC = 105;
string w; // 要找的单词 W（由不同大写字母组成）
int R, C; // 网格行数、列数
char g[MAXRC][MAXRC]; // 网格
int ans = 0;
// 8 个方向：0 上，1 右上，2 右，3 右下，4 下，5 左下，6 左，7 左上
// 在这个编号下，hd + 2 和 hd + 6（对 8 取模）恰好是两个垂直方向
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// 已经匹配了 w[0..pos-1]，当前停在 (x,y)，前进方向是 hd，turned 表示是否转过弯。
// 下一步尝试把 w[pos] 放到下一个格子里：要么继续直走，要么（在还没转过弯时）转 90 度。
void dfs(int pos, int x, int y, int hd, bool turned) {
if (pos == (int)w.size()) { // 整条路径的字母全部匹配成功
ans++;
return;
}
// 不转弯：继续沿 hd 方向走到下一个格子
int nx = x + dx[hd];
int ny = y + dy[hd];
if (nx >= 0 && nx < R && ny >= 0 && ny < C && g[nx][ny] == w[pos]) {
dfs(pos + 1, nx, ny, hd, turned);
}
// 转弯：90 度直角拐弯只能发生一次，且第一段至少要有 2 个字母
//（pos >= 2 表示当前格子是 w[pos-1]，即拐点不在起点上）
if (pos >= 2 && !turned) {
for (int d = 2; d <= 6; d += 4) { // 左转 d=6，右转 d=2，两个垂直方向
int hd2 = (hd + d) % 8;
int tx = x + dx[hd2];
int ty = y + dy[hd2];
if (tx >= 0 && tx < R && ty >= 0 && ty < C && g[tx][ty] == w[pos]) {
dfs(pos + 1, tx, ty, hd2, true);
}
}
}
}
void solve() {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (g[i][j] != w[0]) {
continue;
}
// 从起点 (i,j) 分别向 8 个方向开始匹配
for (int hd = 0; hd < 8; hd++) {
dfs(1, i, j, hd, false);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> w >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> g[i][j];
}
}
solve();
cout << ans << '\n';
return 0;
}复杂度
- main.cpp（DFS 游走）：每个格子 × 8 个初始方向，每条路径深度 ≤ L，每步至多 3 个分支。时间复杂度 O(R·C·8·L)，R=C=100、L=26 时约 2×10^6 次操作。
- brute.cpp（模板枚举）：O(R·C·8·L²)，只适合小数据验证与对拍。
- 空间复杂度均为 O(R·C)（网格 + 递归栈 O(L)）。
总结
本题的考点不是优化，而是把"单词出现"正确地建模成"至多拐一次 90° 弯的路径"并干净地实现。两个关键点：一是枚举起点 + 初始方向后路径形状完全确定，天然去重；二是第一段至少 2 个字母的隐含规则（官方数据验证）。main.cpp 用带 turned 标记的 DFS 沿路径游走，比逐个模板检查的 brute.cpp 少做大量重复前缀比对，也正好对应官方"从每个格子向 8 个方向搜索、记录有没有转弯"的写法。