学习笔记_25_03_05

洛谷P1101 单词方阵

Reference

题目描述

  给一 n×n 的字母方阵，内可能蕴含多个 yizhong 单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉，因此有可能共用字母。输出时，将不是单词的字母用 * 代替，以突出显示单词。

输入格式

  第一行输入一个数 n。(7≤n≤100)。

  第二行开始输入 n×n 的字母矩阵。

输出格式

  突出显示单词的 n×n 矩阵。

输入输出样例

1
2
3
4
5
6
7
8
9
10
输入 #1

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
1
2
3
4
5
6
7
8
9
10
输出 #1

*******
*******
*******
*******
*******
*******
*******

1
2
3
4
5
6
7
8
9
10
11
输入 #2

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg
1
2
3
4
5
6
7
8
9
10
输出 #2

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

解题思路

  本题显然是一道搜索题目，我们重点应该考虑的是如何实现“yizhong”中7个字母的连续搜索。要实现连续搜索的功能，显然我们需要有一个用以验证的数组，在Python中我们可以使用string = "yizhong"这个字符串来逐个验证第i个字母，若有错误就即刻回溯。

  另一个要实现的功能是正确的字母原样输出，不正确的字母输出为*，这个通过开辟副本数组就可以轻松实现，不再赘述。

  以上，再加上DFS算法的基本框架即可实现本题。

解题代码

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

dxs = [1, 1, 1, 0, 0, -1, -1, -1]
dys = [1, 0, -1, 1, -1, 1, 0, -1]

GoalString = "yizhong"

def dfs(x, y):
    for i in range(8): # 枚举8个方向
        flag = 1
        for j in range(1, 7): # 从GoalSting[1]到GoalSting[6]
            nx = x + j * dxs[i] # 这里最妙的是这样保证了朝着一个方向连续搜索
            ny = y + j * dys[i] # 而非8个方向螺旋式地搜索
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                flag = 0
                break
            if arr[nx][ny] != GoalString[j]:
                flag = 0
                break
        if flag == 0:
            continue
        for j in range(7): # 从GoalSting[0]到GoalSting[6]
            nx = x + j * dxs[i] 
            ny = y + j * dys[i]
            ans[nx][ny] = arr[nx][ny] # 将目标数据存到副本数组当中



if __name__ == "__main__":
    n = int(input())
    arr = [['' for i in range(n)] for i in range(n)]
    ans = [[0 for i in range(n)] for i in range(n)]
    for i in range(n):
        InputString = input()
        for j in range(n):
            arr[i][j] = InputString[j] # 这里要注意不要把input写到最里层

    for i in range(n):
        for j in range(n):
            if arr[i][j] == 'y': # 如果遇到y就开始搜索
                dfs(i, j)

    for i in range(n):
        for j in range(n):
            if ans[i][j] == 0:
                ans[i][j] = '*'
            print(ans[i][j],end='')
        print(end='\n')

  成功AC！

学习笔记
#dfs #python #洛谷
学习笔记_25_03_05
http://example.com/2025/03/06/note01/
作者
谢斐
发布于
2025年3月6日
许可协议