刷题笔记合集🔗

单词搜索

问题描述

找到它是一个小游戏，你需要在一个矩阵中找到给定的单词。

假设给定单词 HELLOWORD，在矩阵中只要能找到 H->E->L->L->O->W->O->R->L->D 连成的单词，就算通过。

注意区分英文字母大小写，并且您只能上下左右行走，不能走回头路。

输入格式

输入第 行包含两个整数 分别表示 行 列的矩阵，

第 行是长度不超过 的单词 (在整个矩阵中给定单词 只会出现一次)，

从第 行到第 行是指包含大小写英文字母的长度为 的字符串矩阵。

输出格式

如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置(第几行 第几列)，

否则输出"NO"。

样例输入

5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC

5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
AGRBC

样例输出

3 2

NO

数据范围

• 
• 单词 的长度不超过
• 矩阵中包含大小写英文字母

题解

这道题目是一个经典的矩阵搜索问题，要求在字母矩阵中找到一条能形成目标单词的路径。

具体来说，题目要求：

1. 在一个n×m的字母矩阵中，寻找是否存在一条路径，使得路径上的字母依次连起来刚好形成给定的单词
2. 路径只能沿上下左右四个方向移动，且不能重复经过同一个位置
3. 如果找到这样的路径，输出起始位置（第几行第几列）；否则输出"NO"

解决这类问题的标准做法是回溯搜索（DFS）：

1. 遍历矩阵中的每个位置，尝试将其作为起点
2. 对于每个起点，如果当前字符与单词的第一个字符匹配，则开始深度优先搜索
3. 在搜索过程中，从当前位置向四个方向探索，寻找匹配单词下一个字符的相邻位置
4. 使用一个visited数组来标记已经访问过的位置，避免重复访问
5. 如果能够匹配完整个单词，则找到了答案；否则回溯并尝试其他路径

时间复杂度分析：假设矩阵大小为n×m，单词长度为k，最坏情况下需要尝试矩阵中的每个位置作为起点，每个起点至多探索4^k条路径（因为每一步有4个可能的方向），因此总时间复杂度为O(n×m×4^k)。但实际上，由于剪枝（只有匹配的字符才会继续搜索）和路径不能重复的限制，算法效率会比理论上限好很多。

在本题给定的数据范围内（n,m<21，单词长度≤100），这个解法在实际应用中是高效的。

参考代码

• Python

import sys

# 定义输入函数
input = lambda: sys.stdin.readline().strip()

# 读取输入
n, m = map(int, input().split())  # 矩阵的行数和列数
word = input()  # 目标单词
matrix = [input() for _ in range(n)]  # 字母矩阵

# 四个方向的偏移量：上、右、下、左
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def search_word():
    # 记录已访问的位置
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    # 深度优先搜索函数
    def dfs(row, col, index):
        # 如果已经匹配完整个单词，返回True
        if index == len(word):
            return True
        
        # 如果当前位置越界、已访问或字符不匹配，返回False
        if (row < 0 or row >= n or col < 0 or col >= m or 
            visited[row][col] or matrix[row][col] != word[index]):
            return False
        
        # 标记当前位置为已访问
        visited[row][col] = True
        
        # 在四个方向上继续搜索
        for dr, dc in directions:
            if dfs(row + dr, col + dc, index + 1):
                return True
        
        # 回溯：将当前位置标记为未访问
        visited[row][col] = False
        return False
    
    # 尝试矩阵中的每个位置作为起点
    for i in range(n):
        for j in range(m):
            if dfs(i, j, 0):
                # 找到路径，返回起始位置（题目要求是1-indexed）
                return f"{i+1} {j+1}"
    
    # 没有找到符合条件的路径
    return "NO"

# 输出结果
print(se