单词方阵

形式化题目

给定一个 $n \times n$ 的小写字母矩阵。称一个单词出现为：沿 8 个方向（水平、垂直、两条对角线）中的某一个方向连续排列的 7 个格子，其字符恰好依次为 yizhong，全程方向不变。不同单词可以交叉、共用字母。

要求输出一个同样大小的矩阵：被至少一个单词覆盖的字母原样保留，其余位置全部输出 *。

思路

这道题的枚举检查本身就是最终做法，没有更进一步的优化台阶：每个单词由「起点 + 方向」唯一确定，逐字符核对 7 个位置即可。

关键点有三处：

方向数组：把 8 个方向存成 $(dx, dy)$ 数组，第 $k$ 个字符的位置由公式 $(x + dx \cdot k,\ y + dy \cdot k)$ 给出，比写 8 组坐标判断更不容易漏方向。
起点剪枝：yizhong 只有第 0 位是 y，所以只从字母 y 的格子出发检查，不会漏掉任何单词。
布尔标记处理交叉：一个字母可能属于多个单词，keep 只做 0→1 置位，天然是「至少被一个单词覆盖」的并集。

下图是样例 #2 的输出结果，* 掩码清晰暴露出两条直线单词：

text

1
2
3
4
5
6
7
8*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

观察图中两处亮点：第 1 行的 yizhong 是向右方向的匹配；从 (2,2) 到 (8,8) 的主对角线是向右下方向的匹配。同一个起点、同一个方向只可能命中一次，命中后整条线的 7 个字母全部保留。

代码

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/**
 * 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-13 13:28
 * update_at: 2026-08-13 13:32
 */
/* P1101 单词方阵 */
/* 枚举每个起点与 8 个方向，检查 7 个连续字符是否构成 yizhong。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
char g[MAXN][MAXN];    // 字母方阵
int keep[MAXN][MAXN];  // keep[i][j] = 1 表示该字符属于某个单词
const char word[] = "yizhong";
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };

// 判断以 (x,y) 为起点、沿方向 d 的 7 个字符是否正好是 yizhong。
bool match(int x, int y, int d) {
    for (int step = 0; step < 7; step++) {
        int nx = x + dx[d] * step;
        int ny = y + dy[d] * step;
        if (nx < 1 || nx > n || ny < 1 || ny > n) {
            return false;  // 超出方阵边界
        }
        if (g[nx][ny] != word[step]) {
            return false;  // 字符不匹配
        }
    }
    return true;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> (g[i] + 1);
    }

    // 枚举每个起点和 8 个方向
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            if (g[x][y] != 'y') {
                continue;  // 首字母不是 y，不可能成为单词起点
            }
            for (int d = 0; d < 8; d++) {
                if (match(x, y, d)) {
                    // 匹配成功，标记这 7 个位置（不同单词可交叉共用）
                    for (int step = 0; step < 7; step++) {
                        int nx = x + dx[d] * step;
                        int ny = y + dy[d] * step;
                        keep[nx][ny] = 1;
                    }
                }
            }
        }
    }

    // 属于单词的字符保留原样，其余输出 *
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (keep[i][j]) {
                cout << g[i][j];
            } else {
                cout << '*';
            }
        }
        cout << '\n';
    }

    return 0;
}

复杂度

时间： $O(n^2 \times 8 \times 7) = O(n^2)$ ， $n = 100$ 时约 $5.6 \times 10^5$ 次字符比较。
空间：方阵与标记矩阵各 $O(n^2)$ 。

总结

「固定方向、固定长度」使单词完全由起点和方向确定，于是问题退化为最朴素的枚举 + 逐字符核对，复杂度 $O(n^2)$ 远小于任何限制。这道题还演示了两个可迁移的套路：方向数组 $(dx, dy)$ 是网格题的通用写法；yizhong 首字母唯一、只从 y 出发剪枝，避免把检查点浪费在无意义的位置。rbook 的《字符串朴素匹配》把「枚举起点、逐字符贴模式串」称为朴素匹配，并直接把本题列为其在网格上的经典例题：一维的下一个位置是 i+1，二维则是 (x+dx, y+dy)。

图示解析

这张 ASCII 图串起本题从输入到输出的完整路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14输入：n×n 字母方阵 g
        |
        v
枚举起点 (x, y)
   |-- 首字母不是 'y' → 跳过（剪枝）
   `- 对 8 个方向 (dx, dy)
         |
         v
match(x, y, d)：沿方向走 7 步
   |-- 越界或字符 != yizhong[k] → 该方向失败
   `- 7 步全部通过 → 命中，7 个位置置 keep = 1
         |
         v
输出：keep[i][j] ? g[i][j] : '*'

先看中间的分支：起点剪枝把检查点从全部 $n^2$ 格缩小到只含 y 的格子；再看 match 的失败条件，越界和字符不等都会立即放弃该方向；最后命中动作只有一条，把 7 个位置写进 keep，多个单词共用字母时多次置位不会互相破坏，这正是交叉共用的并集处理。

目录

形式化题目

思路

代码

复杂度

总结

图示解析