import queue

grids = []

################################################################################

grids.append('''\
OOOOOOOOOOOO
OOO        O
OO         O
OO X       O
O   #  #   O
O          O
O          O
O   #  #   O
OO      X OO
OOX       OO
OO     X OOO
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
OOOOOOOOOOOO
OOOOOOOOOOOO
OOO      OOO
OO   ##   OO
OO  O  #  OO
OO        OO
OO   XX   OO
OOO      OOO
OOOOOOOOOOOO
OOOOOOOOOOOO
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O          O
O          O
O  #    #  O
O          O
O          O
O          O
O          O
O X     #  O
O          O
O          O
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O    O    OO
O       # OO
O         OO
O         OO
OOX      OOO
O         OO
O        #OO
O         OO
O    O   OOO
OOOOOOOOOOOO
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O O      O O
O  #       O
O        # O
O       X  O
O          O
O          O
O  #       O
O       #  O
O          O
O          O
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O          O
O   O   #  O
O         OO
O          O
O          O
O        X O
O          O
O        # O
O #        O
O          O
OOOOOOOOOOOO''')

################################################################################

def reader(grid):
    walls = set()
    blocks = set()
    targets = set()
    for y, line in enumerate(grid.split('\n')):
        for x, char in enumerate(line):
            if char == 'O':
                walls.add((y, x))
            elif char == '#':
                blocks.add((y, x))
            elif char == 'X':
                targets.add((y, x))
    return walls, blocks, targets

def worker(walls, blocks, targets):
    states = {frozenset(blocks)}
    jobs = queue.Queue()
    jobs.put((blocks, None))
    while not jobs.empty():
        job = jobs.get()
        # Pick a block to move.
        for block in job[0]:
            # Move up.
            offset = 1
            temp = (block[0] - offset, block[1])
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0] - offset, block[1])
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0] - offset, block[1]))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
            # Move down.
            offset = 1
            temp = (block[0] + offset, block[1])
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0] + offset, block[1])
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0] + offset, block[1]))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
            # Move left.
            offset = 1
            temp = (block[0], block[1] - offset)
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0], block[1] - offset)
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0], block[1] - offset))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
            # Move right.
            offset = 1
            temp = (block[0], block[1] + offset)
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0], block[1] + offset)
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0], block[1] + offset))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
    print(len(states), 'Unique States')
    print('No Solution Found!')
    return (blocks, None)

def opener(walls, answer, targets):
    if answer[1] is not None:
        opener(walls, answer[1], targets)
    print(render(walls, answer[0], targets))

def render(walls, blocks, targets):
    box = {}
    for y, x in walls:
        if y not in box:
            box[y] = {}
        box[y][x] = 'O'
    for y, x in targets:
        box[y][x] = 'X'
    for y, x in blocks:
        box[y][x] = '#'
    max_y = max(box)
    max_x = 0
    for y in box:
        max_x = max(max_x, max(box[y]))
    lines = []
    for y in range(max_y + 1):
        line = ''
        for x in range(max_x + 1):
            line += box[y].get(x, ' ')
        lines.append(line)
    return '\n'.join(lines)

################################################################################

if __name__ == '__main__':
    walls, blocks, targets = reader(grids[-1])
    answer = worker(walls, blocks, targets)
    opener(walls, answer, targets); input()