DFS题解 | 量子网络穿梭

import sys


def solve(matrix):
    m = len(matrix[0])
    n = len(matrix)

    # 获取一些信息
    # 起点终点，传送门
    si = sj = fi = fj = 0

    # 我们猜测gates只有两个（一对）
    gates = {}
    dist_top = m*n+1

    visited = [[0]*m for i in range(n)]
    dist = [[dist_top]*m for i in range(n)]

    for i in range(n):
        for j in range(m):
            if matrix[i][j] == "S":
                si = i
                sj = j
            if matrix[i][j] == "E":
                fi = i
                fj = j
            if matrix[i][j] == "2":
                gates[(i,j)] = 1
            if matrix[i][j] == "1":
                visited[i][j] = 1

    reach_end = [0]

    def dfs(i, j, cost):
        if i < 0 or i >= n or j < 0 or j >= m:
            return

        if visited[i][j]:
            return
        
        # 如果不能优化距离，就不再重新考虑
        if cost >= dist[i][j]:
            return
        
        dist[i][j] = cost

        # 到达终点
        if matrix[i][j] == "E":
            reach_end[0] = 1
            return

        visited[i][j] = 1

        # 准备去下一个点

        # 如果是未使用过的传送门
        if matrix[i][j] == "2" and gates[(i,j)]:
            for ni,nj in gates.keys():
                if gates[(ni,nj)]:
                    gates[(ni,nj)] = 0
                    dfs(ni, nj, cost)
                    gates[(ni,nj)] = 1

        # 如果是标准通道或者起点或者使用过的传送门
        else:
            cost += 1
            dfs(i+1, j, cost)
            dfs(i-1, j, cost)
            dfs(i, j+1, cost)
            dfs(i, j-1, cost)

        visited[i][j] = 0

    dfs(si, sj, 0)
    if not reach_end[0]:
        return -1

    return dist[fi][fj]

def get_data():
    matrix = []
    i = 0
    for line in sys.stdin:
        if i > 0:
            a = line[:-1]
            matrix.append([aa for aa in a])
        i += 1
    return matrix

matrix = get_data()

print(solve(matrix))

剪枝思路：

使用dist矩阵记录每个位置的历史最佳代价，当dfs遍历到该位置时，查看其当前代价是否优于历史最佳代价，如果相等甚至大于，则立刻返回上一级

传送门设计：

使用哈希表存储，传送门是否被使用过

当角色位于门上时，其行为模式会根据门是否被使用过而有区别。对于使用过的门，角色位于此处意味着它从门的另一边传送而来，此时应尝试向四周移动而不是再传送回去。这里若不使用标记进行区分会导致程序无限递归。