"""Two robots, exact: breadth-first search over (A's field, B's field, cleaned fields).

With collide=True the robots may never share a field or swap places in one step (following is
fine). Only practical for tiny rooms (about 14 floor fields).
"""
from shortest_route_fast import DIRS
from two_robots import parse_two


def solution(room, collide):
    a, b, floor = parse_two(room)
    cells = sorted(floor)
    index = {cell: i for i, cell in enumerate(cells)}
    full = (1 << len(cells)) - 1
    options = [[(i, '.')] + [(index[(r + dr, c + dc)], go) for dr, dc, go in DIRS if (r + dr, c + dc) in index]
               for i, (r, c) in enumerate(cells)]

    first = (index[a], index[b], 1 << index[a] | 1 << index[b])
    if first[2] == full:
        return '', ''
    parent = {first: None}
    layer = [first]
    while layer:
        nxt = []
        for state in layer:
            ia, ib, mask = state
            for ja, go_a in options[ia]:
                for jb, go_b in options[ib]:
                    if collide and (ja == jb or (ja == ib and jb == ia)):
                        continue
                    new = (ja, jb, mask | 1 << ja | 1 << jb)
                    if new in parent:
                        continue
                    parent[new] = (state, go_a, go_b)
                    if new[2] == full:
                        return rebuild(parent, new)
                    nxt.append(new)
        layer = nxt
    raise ValueError('the robots cannot clean this room')


def rebuild(parent, state):
    a_moves, b_moves = [], []
    while parent[state]:
        state, go_a, go_b = parent[state]
        a_moves.append(go_a)
        b_moves.append(go_b)
    return ''.join(reversed(a_moves)).rstrip('.'), ''.join(reversed(b_moves)).rstrip('.')