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

import sys;input = sys.stdin.readline
from collections import deque as dq

n, m = map(int, input().split())
arr = [list(map(str, input().rstrip())) for _ in range(n)]
for i in range(n):
    for j in range(m):
        if arr[i][j] == '0':
            sx, sy = i, j
            arr[i][j] = '.'


def bfs(x, y):
    q = dq([(x, y, 0, 0)])
    visit = [[[0] * (1 << 6) for _ in range(50)] for _ in range(50)]
    visit[x][y][0] = 1

    while q:
        x, y, cnt, key = q.popleft()
        if arr[x][y] == '1':
            print(cnt)
            return
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + dx, y + dy
            if nx in range(n) and ny in range(m):
                if not visit[nx][ny][key]:
                    if arr[nx][ny] in ['1', '.']:
                        visit[nx][ny][key] = 1
                        q.append((nx, ny, cnt + 1, key))

                    elif 'a' <= arr[nx][ny] <= 'f':
                        n_key = (1 << (ord(arr[nx][ny]) - ord('a'))) | key
                        visit[nx][ny][n_key] = 1
                        q.append((nx, ny, cnt + 1, n_key))

                    elif 'A' <= arr[nx][ny] <= 'F':
                        if key & (1 << (ord(arr[nx][ny]) - ord('A'))):
                            visit[nx][ny][key] = 1
                            q.append((nx, ny, cnt + 1, key))

    print(-1)
    return


bfs(sx, sy)