12

def haspathCore(martrix, rows, cols, row, col, visited, findstr, pathlenth):
    # cur_ch=findstr[pathlenth]
    if pathlenth == len(findstr):  # 找到最后一个字符停止查找
        return True

    hasPath = False
    if (row >= 0 and col >= 0 and row <= rows and col <= cols and findstr[pathlenth] == martrix[row][col] and not
    visited[row][col]):
        # 保证row和col在查找的矩阵索引中；找到符合的str，pathlenght++;并且visited还是false
        pathlenth += 1
        # 走过的置为True
        visited[row][col] = True
        # 递归向该 字符的上下左右分别查找
        # 递归是找当前元素的上下左右的元素
        hasPath = haspathCore(martrix, rows, cols, row - 1, col, visited, findstr, pathlenth) or 
                  haspathCore(martrix, rows, cols, row + 1, col, visited, findstr, pathlenth) or 
                  haspathCore(martrix, rows, cols, row, col - 1, visited, findstr, pathlenth) or 
                  haspathCore(martrix, rows, cols, row, col + 1, visited, findstr, pathlenth)

        if (not hasPath):
            # 将走过的路置为false
            pathlenth -= 1
            visited[row][col] = False

    return hasPath


def hasPath(martrix, findstr):
    if not martrix or not martrix[0] or not findstr:
        raise ValueError('invalid')

    rows = len(martrix)
    cols = len(martrix[0])

    visited = []

    for row in range(rows):
        tmp = []
        for col in range(cols):
            tmp.append(False)
        visited.append(tmp)

    pathlenth = 0
    for row in range(rows):
        for col in range(cols):  # 2层for循环走矩阵的每一个元素
            if (haspathCore(martrix, rows, cols, row, col, visited, findstr, pathlenth)):
                return True

    del visited

    return False


matrix = [
    ['a', 'a', 't', 'g'],
    ['c', 'f', 'c', 's'],
    ['j', 'd', 'e', 'h']
]
findstr = 'at'
print(hasPath(matrix, findstr))