6.矩阵中的路径

题目描述：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如：

包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

代码

import numpy as np


class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.dir = 1

    def get_dir(self):
        return self.dir

    def change_dir(self):
        self.dir += 1


def dfs(matrix, path):
    visit = [[0]*len(matrix[0]) for i in range(len(matrix))]
    starts = []
    for i in range(len(matrix)):  # 计算起始字符的索引
        for j in range(len(matrix[0])):
            if matrix[i][j] == path[0]:
                starts.append((i, j))

    if len(starts) == 0:
        return False

    for (start_x, start_y) in starts: #遍历所有起始字符
        stack = [Node(start_x, start_y)]
        index = 1

        while(stack):
            node = stack[-1]
            x = node.x
            y = node.y
            direction = node.get_dir()
            visit[x][y] = 1  # 避免重复访问

            if direction == 1:
                if x+1 < len(matrix) and matrix[x+1][y] == path[index] and visit[x+1][y] == 0:#不越界，下一个对应路径的下一个字符串，且在当前路径没有访问过
                    index += 1 #路径索引加1
                    if index == len(path)-1:#判断所有路径字符是否都访问过
                        return True
                    stack.append(Node(x+1, y))#将当前路径字符压如栈中
                node.change_dir()#转换方向
                continue

            elif direction == 2:
                if x-1 > 0 and matrix[x-1][y] == path[index] and visit[x-1][y] == 0:
                    index += 1
                    if index == len(path)-1:
                        return True
                    stack.append(Node(x-1, y))
                node.change_dir()
                continue

            elif direction == 3:
                if y-1 > 0 and matrix[x][y-1] == path[index] and visit[x][y-1] == 0:
                    index += 1
                    if index == len(path)-1:
                        return True
                    stack.append(Node(x, y-1))
                node.change_dir()
                continue

            elif direction == 4:
                if y+1 < len(matrix[0]) and matrix[x][y+1] == path[index] and visit[x][y+1] == 0:
                    index += 1
                    if index == len(path)-1:
                        return True
                    stack.append(Node(x, y+1))
                node.change_dir()
                continue

            node = stack.pop()#如果当前节点所有方向都访问过，则该节点出栈
            visit[node.x][node.y] = 0 #将该节点访问锁解除
            index -= 1
    return False


if __name__ == "__main__":
    puzzle = list("ABCESFCSADEE")
    puzzle = np.asarray(puzzle).reshape(3, 4)
    path = "ABCCED"

    print(dfs(puzzle, path))