import re

b = ". X . . ;a X b . ;. C cB A"

def show(b):
    return '\n'.join(b.split(";"))
    
def move(piece, b, dx, dy):
    board = [r[:] for r in b]
    n, m = len(board), len(board[0])
    for i in range(n):
        for j in range(m):
            if board[i][j] == piece:
                x, y = i, j
                break
    X, Y = x, y
    while 0 <= x + dx < n and 0 <= y + dy < m and board[x + dx][y + dy] == '.':
        x += dx
        y += dy
    board[X][Y] = '.'
    board[x][y] = piece
    return ";".join(''.join(r) for r in board)

def solve(b):
    pieces = re.findall(r"[A-WYZ]", b)
    board = [[x for x in r.split(' ') if len(x)] for r in b.split(';')]
    print(board)
    n, m = len(board), len(board[0])
    pos = {}
    for i in range(n):
        for j in range(m):
            p = board[i][j]
            if re.match(r"[a-z]", p[0]):
                pos[p[0].upper()] = (i, j)
                board[i][j] = '.' if len(p) == 1 else p[1]
    _b = ";".join(''.join(r) for r in board)
    print(pieces)
    print(show(_b))
    print(pos)
    seen = set()
    queue = [(_b, 0)]
    while queue:
        ele, lvl = queue.pop(0)
        # print(show(ele))        
        seen.add(ele)
        _board = [list(r) for r in ele.split(';')]
        _pos = {}
        for i in range(n):
            for j in range(m): 
                _p = _board[i][j]
                if re.match(r"[A-WYZ]", _p):
                    _pos[_p] = (i, j)
        # print(_pos)
        # print('\n\n')
        if all(pos[p] == _pos[p] for p in pos):
            return lvl
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for piece in pieces:
                nb = move(piece, _board, dx, dy)
                if not nb in seen:
                    queue.append((nb, lvl + 1))
                    seen.add(nb)

        
ans = solve(b)
print(ans)