Baekjoon-1194-달이 차오른다, 가자.

import sys
input = sys.stdin.readline
from collections import deque
from itertools import combinations

N,M = map(int, input().split())

# build map
maps = []
minsic = []
ext = []
keys = {k:[] for k in 'abcdef'}
doors = {k:[] for k in 'ABCDEF'}
for i in range(N):
    line = [c for c in input().strip()]
    maps.append(line)
    for j,c in enumerate(line):
        if c == '0':
            minsic = [i,j]
            maps[i][j] = '.'
        if c == '1':
            ext.append([i,j])
        if c in keys.keys():
            keys[c].append([i,j])
        if c in doors.keys():
            doors[c].append([i,j])

# visited 를 각 열쇠 조합 마다 만들기 
possible_keys = []
for i in range(1,6):
    possible_keys += list(combinations('abcdef',i))
visited = {''.join(k):[[-1] * M for _ in range(N)] for k in possible_keys}
visited[''] = [[-1] * M for _ in range(N)]
visited['abcdef'] = [[-1] * M for _ in range(N)]

q = deque([minsic+['']])
visited[''][minsic[0]][minsic[1]] = 0
while q:
    x,y,k = q.popleft()
    for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
        nx,ny = x+dx,y+dy
        if 0<=nx<N and 0<=ny<M and visited[k][nx][ny]==-1:
            if maps[nx][ny] in 'abcdef':
                if maps[nx][ny] not in k:
                    new_k = ''.join(sorted(k+maps[nx][ny]))
                else:
                    new_k = k
                q.append([nx,ny,new_k])
                visited[new_k][nx][ny] = visited[k][x][y] + 1
            elif maps[nx][ny]=='.' or maps[nx][ny] in k.upper():
                q.append([nx,ny,k])
                visited[k][nx][ny] = visited[k][x][y] + 1
            elif maps[nx][ny] == '1':
                print(visited[k][x][y]+1)
                exit()

print(-1)