单词方阵

题意

在字母方阵中寻找所有沿同一方向连续出现的 yizhong。保留属于任意一个单词的字符，其余位置输出 *。

思路

枚举起点 (x,y) 和八个方向 (dx,dy)。第 step 个字符应位于 (x+dx*step,y+dy*step)。

先生成七个坐标，再用 all 同时检查边界和字符。如果全部匹配，就把这七个位置标记。不同单词可以交叉，因此只将标记从假改为真，不会互相覆盖。

Python 知识

双层列表推导式生成八个方向，并排除 (0,0)。
zip(positions,word) 同时遍历坐标与目标字符。
all(...) 遇到第一个越界或字符不符就短路停止。
输出时用嵌套 zip 和生成器选择原字符或 *。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：all 的短路判断。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：列表推导式和整体判定。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24n = int(input())
grid = [input().strip() for _ in range(n)]
word = "yizhong"
marked = [[False] * n for _ in range(n)]
directions = [
    (dx, dy)
    for dx in (-1, 0, 1)
    for dy in (-1, 0, 1)
    if (dx, dy) != (0, 0)
]

for x in range(n):
    for y in range(n):
        for dx, dy in directions:
            positions = [(x + dx * step, y + dy * step) for step in range(7)]
            if all(
                0 <= row < n and 0 <= col < n and grid[row][col] == letter
                for (row, col), letter in zip(positions, word)
            ):
                for row, col in positions:
                    marked[row][col] = True

for row, flags in zip(grid, marked):
    print("".join(letter if keep else "*" for letter, keep in zip(row, flags)))

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1101 单词方阵 */
/* 枚举每个格子作为起点和八个方向，检查是否为 yizhong。 */

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

const int MAXN = 105;

int n;
char g[MAXN][MAXN]; // 字母方阵
int mark[MAXN][MAXN]; // 标记属于单词的字符
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 };

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

    // 枚举每个起点和八个方向
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            for (int d = 0; d < 8; d++) {
                bool ok = true;
                // 检查 yizhong 是否沿方向 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) {
                        ok = false;
                        break;
                    }
                    if (g[nx][ny] != word[step]) {
                        ok = false;
                        break;
                    }
                }
                // 匹配成功，标记这七个位置
                if (ok) {
                    for (int step = 0; step < 7; step++) {
                        int nx = x + dx[d] * step;
                        int ny = y + dy[d] * step;
                        mark[nx][ny] = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (mark[i][j])
                cout << g[i][j];
            else
                cout << '*';
        }
        cout << "\n";
    }
    return 0;
}

复杂度

每个格子检查八个方向，每次固定七个字符，时间复杂度为 $O(n^2)$ ，标记矩阵空间为 $O(n^2)$ 。

总结

方向一旦选定，七个坐标就由一个统一公式产生；用 all 写整体匹配，比七层手工判断更短也更不容易漏方向。

目录

题意

思路

Python 知识

代码

复杂度

总结