65 矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左、右、上、下移动一个格子。一个路径不能重复进入同一个格子。

解题思路

核心思想：DFS回溯。

时间复杂度：O(mn3^k) 空间复杂度：O(k)

Python 实现

def has_path(matrix, path):
    """
    判断矩阵中是否存在某条路径

    Args:
        matrix: 二维矩阵
        path: 路径字符串

    Returns:
        bool: 是否存在
    """
    if not matrix or not matrix[0] or not path:
        return False

    rows, cols = len(matrix), len(matrix[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(row, col, index):
        # 找到完整路径
        if index == len(path):
            return True

        # 越界或已访问
        if row < 0 or row >= rows or col < 0 or col >= cols or visited[row][col]:
            return False

        # 字符不匹配
        if matrix[row][col] != path[index]:
            return False

        # 标记访问
        visited[row][col] = True

        # 四个方向搜索
        found = (dfs(row - 1, col, index + 1) or
                 dfs(row + 1, col, index + 1) or
                 dfs(row, col - 1, index + 1) or
                 dfs(row, col + 1, index + 1))

        # 回溯
        visited[row][col] = False

        return found

    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return True

    return False


# 测试代码
if __name__ == "__main__":
    matrix = [
        ['a', 'b', 't', 'g'],
        ['c', 'f', 'c', 's'],
        ['j', 'd', 'e', 'h']
    ]

    print(f"矩阵中是否有'bfce': {has_path(matrix, 'bfce')}")
    print(f"矩阵中是否有'abtg': {has_path(matrix, 'abtg')}")

# 输出:
# 矩阵中是否有'bfce': True
# 矩阵中是否有'abtg': False