"""Starter bot for StrategyBot Cutline. Upload this file as it is, then make it better.

Your file needs one function, act(state), that returns one of
NORTH, EAST, SOUTH, WEST, STAY. It gets called once per turn.
Anything you print() shows up in your bot's log, not in the game.

state (all coordinates are [x, y], x = column, y = row, [0, 0] top-left):
  turn, turns_remaining, turns, width, height
  owner[y][x]       -1 = neutral, otherwise the id of the bot that owns it
  walls             cells nobody can enter
  pads              each bot's protected 2x2 start; you can't enter a rival's pad
  self              your bot: id, position, trail (oldest first), returning, area, score, blocked
  bots              all four bots, the same fields
  priority_seat     who wins a tie for an empty cell this turn
  legal_actions     the actions you may take right now

This bot walks out of its land, takes a few steps, and heads straight back
to close the loop. If a rival's open trail is right next to it, it cuts it.
"""
from collections import deque

DIRS = {"NORTH": (0, -1), "EAST": (1, 0), "SOUTH": (0, 1), "WEST": (-1, 0)}
LOOP_LENGTH = 3  # steps outside your land before turning back; longer = more land, more risk


def first_step(s, start, goals, avoid):
    """Breadth-first search: the first action on a shortest path from start to any goal cell."""
    first = {start: None}
    todo = deque([start])
    while todo:
        c = todo.popleft()
        for name, (dx, dy) in DIRS.items():
            n = (c[0] + dx, c[1] + dy)
            if not (0 <= n[0] < s["width"] and 0 <= n[1] < s["height"]) or n in first or n in avoid:
                continue
            first[n] = first[c] or name
            if n in goals:
                return first[n]
            todo.append(n)
    return None


def act(state):
    me = state["self"]
    if me["returning"]:
        return "STAY"  # your trail was cut: the server drives you home

    pos = tuple(me["position"])
    mine = {(x, y) for y, row in enumerate(state["owner"]) for x, v in enumerate(row) if v == me["id"]}
    avoid = {tuple(c) for c in state["walls"]}
    avoid |= {tuple(c) for i, pad in enumerate(state["pads"]) if i != me["id"] for c in pad}
    avoid |= {tuple(b["position"]) for b in state["bots"] if b["id"] != me["id"]}
    trail = {tuple(c) for c in me["trail"]}

    # a rival's open trail one step away: step on it (not on the rival itself)
    rival_trail = {tuple(c) for b in state["bots"] if b["id"] != me["id"] for c in b["trail"][:-1]}
    for name, (dx, dy) in DIRS.items():
        if (pos[0] + dx, pos[1] + dy) in rival_trail and name in state["legal_actions"]:
            return name

    # out long enough: go home without crossing your own trail, so the loop encloses land
    if len(trail) >= LOOP_LENGTH:
        step = first_step(state, pos, mine, avoid | trail) or first_step(state, pos, mine, avoid)
    else:
        outside = {(x, y) for y in range(state["height"]) for x in range(state["width"])} - mine - trail - avoid
        step = first_step(state, pos, outside, avoid | trail)
    return step if step in state["legal_actions"] else "STAY"