大学Python习题 编写一个能搜索单词的程序，函数名为def exist(board: List[List[str]], word: str)

在大学Python学习中，编写这样的单词搜索程序可以锻炼学生的列表操作、字符串处理和遍历理解能力。`exist` 函数的作用是在给定的二维字符网格 `board` 中查找是否存在指定的单词 `word`。这个函数通常需要采用宽度优先搜索（广度优先搜索）或深度优先搜索算法来逐行逐列地检查每个字符是否匹配，并保持追踪已访问的位置。

这是一个简单的示例实现：

from typing import List

def is_valid(i, j, board):
    # 检查索引是否越界并确保当前位置不是空格
    return 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] != ' '

def exist(board: List[List[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    
    def dfs(i, j, current_word=()):
        # 初始化当前路径为空串
        if current_word == (word,):
            return True
        
        # 搜索上下左右四个方向
        for dx, dy in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
            ni, nj = i + dx, j + dy
            if is_valid(ni, nj) and board[ni][nj] == current_word[-1]:
                new_word = current_word[:-1] + (board[ni][nj],)
                if dfs(ni, nj, new_word):
                    return True
                
        return False
    
    # 从每个位置开始搜索
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == word[0]:
                if dfs(i, j):
                    return True
                    
    # 如果都没有找到，返回False
    return False

# 示例
board = [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']]
word = "ABCCED"
print(exist(board, word))  # 输出：True