"""Fewest commands, exact: breadth-first search over (robot's field, set of cleaned fields).

Guaranteed shortest, but the number of states explodes with room size, so it gives up and
returns None after max_states states.
"""
import shortest_route_fast
from shortest_route_fast import DIRS, lower_bound, parse


def solution(room, max_states=1_000_000):
    fast = shortest_route_fast.solution(room)
    if len(fast) <= lower_bound(room):
        return fast                             # the fast route is already proven shortest

    start, floor = parse(room)
    cells = sorted(floor)
    index = {cell: i for i, cell in enumerate(cells)}
    full = (1 << len(cells)) - 1
    black = sum(1 << i for i, (r, c) in enumerate(cells) if (r + c) % 2 == 0)
    moves = [[(index[(r + dr, c + dc)], go) for dr, dc, go in DIRS if (r + dr, c + dc) in index]
             for r, c in cells]

    first = (index[start], 1 << index[start])
    parent = {first: None}
    layer = [first]
    for k in range(1, len(fast)):               # only routes shorter than the fast one matter
        nxt = []
        for state in layer:
            i, mask = state
            for j, go in moves[i]:
                new = (j, mask | 1 << j)
                if new in parent:
                    continue
                left = full & ~new[1]
                same = bin(left & (black if black >> j & 1 else ~black)).count('1')
                other = bin(left).count('1') - same
                # the next steps alternate colours starting from the other colour
                if k + max(same + other, 2 * same, 2 * other - 1) >= len(fast):
                    continue
                parent[new] = (state, go)
                if new[1] == full:
                    return rebuild(parent, new)
                nxt.append(new)
        if len(parent) > max_states:
            return None
        layer = nxt
    return fast                                 # nothing shorter exists


def rebuild(parent, state):
    out = []
    while parent[state]:
        state, go = parent[state]
        out.append(go)
    return ''.join(reversed(out))