"""Starter bot for StrategyBot Territory. 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, RETREAT. 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, width, height, cell_cap
  owner[y][x]       -1 = neutral, otherwise the id of the bot that owns it
  self              your bot: id, position, home, capture_target, dwell_remaining, owned_count
  bots              all four bots, the same fields plus alive
  priority_seat     who wins a tie for an empty cell this turn
  legal_actions     the actions you may take right now
"""
import random
from collections import deque

DIRS = {"NORTH": (0, -1), "EAST": (1, 0), "SOUTH": (0, 1), "WEST": (-1, 0)}


def neighbours(s, c):
    for name, (dx, dy) in DIRS.items():
        x, y = c[0] + dx, c[1] + dy
        if 0 <= x < s["width"] and 0 <= y < s["height"]:
            yield name, (x, y)


def best_move(s, score):
    """Walk through your own land, then step into the non-owned cell with the best score(cell, dist)."""
    me = s["self"]["id"]
    start = tuple(s["self"]["position"])
    others = {tuple(b["position"]) for b in s["bots"] if b["alive"] and b["id"] != me}
    first = {start: None}  # own cell -> first action taken to reach it
    dist = {start: 0}
    todo = deque([start])
    best, best_val = "STAY", None
    while todo:
        c = todo.popleft()
        for name, n in neighbours(s, c):
            if n in others or n in dist:
                continue
            act = first[c] or name
            if s["owner"][n[1]][n[0]] == me:
                first[n] = act
                dist[n] = dist[c] + 1
                todo.append(n)
            else:
                val = score(n, dist[c] + 1)
                if val is not None:
                    val += random.random() * 0.3  # breaks ties, so two bots don't mirror each other forever
                if val is not None and (best_val is None or val > best_val):
                    best, best_val = act, val
    return best


def act(state):
    if state["self"]["capture_target"]:
        return "STAY"  # finish the capture

    me = state["self"]["id"]

    def score(cell, dist):
        x, y = cell
        mine_next_to_it = sum(state["owner"][ny][nx] == me for _, (nx, ny) in neighbours(state, cell))
        neutral = state["owner"][y][x] == -1
        return (2 if neutral else 1) + mine_next_to_it - 0.5 * dist

    return best_move(state, score)