from dataclasses import dataclass, field
from typing import ClassVar
from functools import cached_property
from itertools import chain

class GameSetup:
    goalX  = 1
    goalY = 2
    grid = ["...", ".X.",'...']


@dataclass(eq=True, order=True)
class Move(GameSetup):
    x: int = field(hash=True, compare=False)
    y: int = field(hash=True, compare=False)
    step:int  = field(default=0, hash=False, compare=True)
    cost:float = field(init=False, hash=False, compare=True)

    def __post_init__(self):
        self.cost = self.get_cost()
    
    def __hash__(self):
        return hash((self.x, self.y))

    @property
    def maxX(self):
        return len(GameSetup.grid)-1
    
    @property
    def maxY(self):
        return len(GameSetup.grid[0])-1

    def get_cost(self) -> float:
        if self.x > self.maxX or self.x < 0 or self.y > self.maxY or self.y < 0:
            scost = 1e9
        elif Move.grid[self.x][self.y] == 'X':
            scost = 1e9
        else:
            scost = (self.goalX-self.x) ** 2 + (self.goalY-self.y) ** 2
        return scost
        
    def all_moves(self):
        row = GameSetup.grid[self.x]
        col = ''.join([r[self.y] for r in GameSetup.grid])
        x_min = max(0, col.rfind('X', 0, self.x))
        xx = col.find('X', self.x)
        if xx == -1:
            xx = self.maxX
        x_max = min(self.maxX, xx)
        print(col, x_min, x_max)
        y_min = max(0, row.rfind('X', 0, self.y))
        yy = row.find('X', self.y)
        print(row, yy)
        if yy == -1:
            yy = self.maxY
        print(self.maxY, yy)
        y_max = min(self.maxY, yy)
        ret = []
        print(x_min, x_max, y_min, y_max)

        for y in chain(range(y_min, self.y), range(self.y+1, y_max+1)):
            ret.append(Move(self.x, y, self.step+1))
        for x in chain(range(x_min, self.x), range(self.x+1, x_max+1)):
            ret.append(Move(x, self.y, self.step+1))
        return re
def minimumMoves(grid, startX, startY, goalX, goalY):
    # Write your code here
    GameSetup.goalX = goalX
    GameSetup.goalY = goalY
    GameSetup.grid = grid
    moves = [Move(startX, startY, 0)]
    processed = set()
    
    while moves:
        move = heapq.heappop(moves)
        #move = moves[-1]
        print(f"current_{move=}")
        processed.add(tuple((move.x, move.y)))
        startX = move.x
        startY = move.y
        step = move.step
        if (startX, startY) == (goalX, goalY):
            return step
        next_moves = move.all_moves()
        valid_moves = [m for m in next_moves if m.cost < 1e9 and tuple((m.x, m.y)) not in processed]
        #valid_moves = sorted(valid_moves, reverse=True)
        for v in valid_moves:
            processed.add((v.x, v.y))
        moves.extend(valid_moves)
        heapq.heapify(moves)
        print(f"{moves=}")
        print(f"{processed=}"