迷宫寻路

# 读取输入数据
[M,N]= list(map(int,input().split()))
maxz = []
for x in range(M):
    maxz.append(list(input()))

# -------------------------------------------------
# M=5
# N=5
# maxz=[['0','2','1','1','1'],
#       ['0','1','a','0','A'],
#       ['0','1','0','0','3'],
#       ['0','1','0','0','1'],
#       ['0','1','1','1','1']]
# -------------------------------------------------
# 数据初始化

start0 = []
end0 = []

# 提取所有带字母的钥匙和门
dicta = []
dictb = []

for x in range(M):
    for y in range(N):
        if maxz[x][y] == '2':
            start0 = [x, y]
        elif maxz[x][y] == '3':
            end0 = [x, y]
        elif 96 < ord(maxz[x][y]) < 123&nbs***bsp;64 < ord(maxz[x][y]) < 91:
            dicta.append([maxz[x][y], x, y])

# 按钥匙字母排序
dicta.sort(key=lambda x: x[0])
lena = len(dicta)

# 转换成钥匙和门的组合
for x in range(lena // 2):
    dictb.append(dicta[(lena // 2) + x][1:3])
    dictb.append(dicta[x][1:3])

# ---------------------------------------------------------

# 计算 G,H,F,P值   G为当前点到起点的距离，H为当前点到终点的距离，F为G+H，P为来源点
def distance(Node_current7, yuandian, start8, end8):
    P = yuandian
    G = abs(Node_current7[0] - start8[0]) + abs(Node_current7[1] - start8[1])
    H = abs(Node_current7[0] - end8[0]) + abs(Node_current7[1] - end8[1])
    F = G + H
    return [F, P]

# 查找周围的临接点
def findNeighbors(nc, maxz9, Node_start7, Node_end7):
    open_list9 = []

    if nc[0] > 0:  # 取上面的点
        if maxz9[nc[0] - 1][nc[1]] != '0':
            open_list9.append([nc[0] - 1, nc[1], distance([nc[0] - 1, nc[1]], nc[0:2], Node_start7, Node_end7)])
    if nc[0] < M - 1:  # 取下面的点
        if maxz9[nc[0] + 1][nc[1]] != '0':
            open_list9.append([nc[0] + 1, nc[1], distance([nc[0] + 1, nc[1]], nc[0:2], Node_start7, Node_end7)])
    if nc[1] > 0:  # 取左面的点
        if maxz9[nc[0]][nc[1] - 1] != '0':
            open_list9.append([nc[0], nc[1] - 1, distance([nc[0], nc[1] - 1], nc[0:2], Node_start7, Node_end7)])
    if nc[1] < (N - 1):  # 取右面的点
        if maxz9[nc[0]][nc[1] + 1] != '0':
            open_list9.append([nc[0], nc[1] + 1, distance([nc[0], nc[1] + 1], nc[0:2], Node_start7, Node_end7)])
    return open_list9

# 从openlist找到F值最小
def findMinNode(openlist_temp):
    y1 = openlist_temp[0]
    for x1 in openlist_temp:
        if y1[2][0] > x1[2][0]:
            y1 = x1
    return y1

# A*搜索
def aStarSearch(Node_start, Node_end, maxz0):
    OpenList = []
    CloseList = []
    Node_current = []
    List_neighbors = []
    term_result = []

    #     把起点加入 open list
    OpenList.append([Node_start[0], Node_start[1], [0, [-1, -1]]])
    #     主循环，每一轮检查一个当前方格节点
    while len(OpenList) > 0:
        # 在OpenList中查找 F值最小的节点作为当前方格节点
        Node_current = findMinNode(OpenList)
        # 当前方格节点从open list中移除
        OpenList.remove(Node_current)
        # 当前方格节点进入 close list
        CloseList.append(Node_current)

        # 找到所有邻近节点
        List_neighbors = findNeighbors(Node_current, maxz0, Node_start, Node_end)
        for x in List_neighbors:
            if (x not in OpenList) & (x not in CloseList):
                # 邻近节点不在OpenList,CloseList中，标记父亲、G、H、F，并放入OpenList
                OpenList.append(x)

        # 如果终点在OpenList中，直接返回路径
        for x in OpenList:
            if Node_end == x[0:2]:  # 如果找到
                term_result.append(x[0:2])
                temp0 = x
                while Node_start != temp0[0:2]:
                    for z in CloseList:
                        if temp0[2][1] == z[0:2]:
                            temp0 = z
                            term_result.append(temp0[0:2])
                            break
                term_result.pop()
                # print(term_result[::-1])
                return len(term_result)

    # OpenList用尽，仍然找不到终点，说明终点不可到达，返回空
    return None


#逐个遍历各个位置，从起点 到第一个钥匙，然后再到第一个门，如果有其他钥匙，再循环，最后去出口。循环计算两点间的距离。
dictb.insert(0, start0)
dictb.append(end0)
sum0 = 0

for y in range(len(dictb) - 1):
    sum0 += aStarSearch(dictb[y], dictb[y + 1], maxz)

print(sum0)