藏宝图

题目描述

在一张由大写字母组成的 $R \times C\ (1 \le R, C \le 100)$ 网格藏宝图中，统计单词 $W$ （长度至少为 2，由互不相同的大写字母组成）按顺序连续出现的次数。一次出现中，字母要么全在同一条直线（横、竖或对角方向，可正向可反向）上，要么前一部分在一条直线上、剩下的字母在与之垂直的第二条直线上，形成一个 90° 直角拐弯（第一段至少 2 个字母，同一格子的同一种摆放只计一次）。

输入：第一行为单词 $W$ ，第二行为 $R$ ，第三行为 $C$ ，接下来 $R$ 行每行 $C$ 个用空格隔开的大写字母。输出一个整数，表示单词出现次数。

样例 1：在下面 5 行 7 列的网格中，单词 MENU 共出现 3 次。

text

1
2
3
4
5F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

思路

把每次出现看成一条"至多拐一次 90° 弯"的路径：枚举起点（内容为 $W[0]$ 的格子）和初始方向，出现的位置就完全确定，天然不重不漏，反向读取也被枚举覆盖。从每个起点沿 8 个方向 DFS 逐格匹配，用 turned 标记保证整条路径至多转一次弯，且拐点不能是起点（第一段至少 2 个字母）。时间复杂度 $O(R \cdot C \cdot 8 \cdot L)$ ，本题数据小轻松通过。

参考代码

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/**
 * 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;
}

目录

题目描述

思路

参考代码