import tiles as R, sys, json
from collections import defaultdict
def ang(room):
    a=defaultdict(int)
    for t in room:
        for v in t: a[v]+=R.angle_units(t,v)
    return a
def violations(room,S,D):
    a=ang(room); out=[]
    for v,x in a.items():
        if v in (S,D):
            if x!=8: out.append(v)
        elif x in (4,8): out.append(v)
    return out
def edge_adjacent(u,room):
    return any(len(set(u)&set(t))==2 for t in room)
best=[None]
def dfs(room,core,S,D,depth,seen):
    key=frozenset(room)
    if key in seen: return
    seen.add(key)
    v=violations(room,S,D)
    if not v:
        if R.connected(room):
            p=R.polygon(room)
            if p and (best[0] is None or len(p)<len(best[0][1])):
                best[0]=(sorted(room),p); print('found',len(p),'sides',len(room),'tiles',flush=True)
        if R.connected(room): return
    if depth==0: return
    # also need connectivity: if no violations but not connected, add tiles toward D
    targets=v[:1] if v else []
    if not targets:
        return
    x=targets[0]
    for u in R.tiles_at(x):
        if u not in room and edge_adjacent(u,room):
            dfs(room|{u},core,S,D,depth-1,seen)
    for u in R.tiles_at(x):
        if u in room and u not in core:
            dfs(room-{u},core,S,D,depth-1,seen)
S=(1,0); D=(int(sys.argv[1]),int(sys.argv[2])); depth=int(sys.argv[3])
core=set(R.tiles_at(S))|set(R.tiles_at(D))
# straight corridor: tiles whose centroid lies near segment
import math
start=set(core)
sx,sy=S; dx,dy=D
for i in range(min(sx,dx)-1,max(sx,dx)+1):
    for j in range(min(sy,dy)-1,max(sy,dy)+1):
        for t in R.cell_tris(i,j):
            cx=sum(p[0] for p in t)/3; cy=sum(p[1] for p in t)/3
            L=math.hypot(dx-sx,dy-sy); d=abs((dx-sx)*(sy-cy)-(sx-cx)*(dy-sy))/L
            tt=((cx-sx)*(dx-sx)+(cy-sy)*(dy-sy))/L**2
            if d<0.5 and 0<=tt<=1: start.add(R.tile_key(t))
print('start conn',R.connected(start),len(start))
sys.setrecursionlimit(10000)
dfs(start,core,S,D,depth,set())
if best[0]: json.dump({'S':S,'D':D,'tiles':best[0][0],'poly':best[0][1]},open(f'dfs_{D[0]}_{D[1]}.json','w'))