"""Emptying the bag, take all: every field the robot enters goes into the bag.

The cleaned area always stays connected to the dock, so each trip walks over clean floor, bites
off new fields that fit, and walks back. Any cut of a breadth-first tree's preorder works that
way, so try several random trees, cut each one optimally, and keep the best.
"""
import random
from collections import deque

from dirt_common import MOVES, parse
from dock_common import bfs_tree, bounds, build_route, split, tree_order


def clean_path(a, b, cleaned, dirt):
    """Fields along a shortest path from a to b that never enters an uncleaned field before b."""
    def open_to(n):
        return n == b or n in cleaned or dirt.get(n) == 0

    parent, queue = {a: None}, deque([a])
    while b not in parent:
        cell = queue.popleft()
        for dr, dc, _, _ in MOVES:
            n = (cell[0] + dr, cell[1] + dc)
            if n in dirt and n not in parent and open_to(n):
                parent[n] = cell
                queue.append(n)
    path = []
    while b != a:
        path.append(b)
        b = parent[b]
    return path[::-1]


def plan(dock, dirt, capacity, rng):
    """One tree: its order, the walk between consecutive fields, and the best cut into trips."""
    dist, parent = bfs_tree(dock, dirt, rng)
    order = tree_order(dock, dirt, dist, parent, rng)
    cleaned, gaps = {dock}, []
    for k in range(len(order) - 1):
        cleaned.add(order[k])
        gaps.append(len(clean_path(order[k], order[k + 1], cleaned, dirt)))
    moves, trips = split([dirt[f] for f in order], [dist[f] for f in order], gaps, capacity)
    return moves, [[order[i] for i in trip] for trip in trips], parent


def solution(room, capacity, rounds=30, seed=0):
    dock, dirt = parse(room)
    assert capacity >= 5, 'every field must fit in the bag on its own'
    lower, _ = bounds(dirt, bfs_tree(dock, dirt)[0], capacity)
    rng = random.Random(seed)
    best = None
    for r in range(rounds):
        result = plan(dock, dirt, capacity, rng if r else None)   # round 0: the plain tree
        if best is None or result[0] < best[0]:
            best = result
        if best[0] <= lower:
            break
    _, trips, parent = best
    return build_route(dock, trips, parent, lambda a, b, cleaned: clean_path(a, b, cleaned, dirt),
                       pick=False)