from collections.abc import Callable, Iterator
from dataclasses import dataclass
from functools import total_ordering
from sys import stdin
from typing import Self

from utils import Dir, a_star


@total_ordering
@dataclass
class Pos:
    x: int
    y: int
    direction: Dir | None = None

    def __eq__(self, other: object) -> bool:
        if isinstance(other, Pos):
            return (self.x, self.y) == (other.x, other.y)
        return NotImplemented

    def __lt__(self, other: object) -> bool:
        if isinstance(other, Pos):
            return (self.x, self.y) < (other.x, other.y)
        return NotImplemented

    def __hash__(self) -> int:
        return hash((self.x, self.y, self.direction))

    def manhattan(self, other: Self) -> int:
        return abs(self.x - other.x) + abs(self.y - other.y)


def make_neighbours(
    width: int, height: int, min_dist: int, max_dist: int
) -> Callable[[Pos], Iterator[Pos]]:
    def neighbours(p: Pos) -> Iterator[Pos]:
        if p.direction not in {Dir.NORTH, Dir.SOUTH}:
            for dy in range(min_dist, max_dist + 1):
                if p.y - dy < height and p.y - dy >= 0:
                    yield Pos(p.x, p.y - dy, Dir.NORTH)
                if p.y + dy < height and p.y + dy >= 0:
                    yield Pos(p.x, p.y + dy, Dir.SOUTH)
        if p.direction not in {Dir.EAST, Dir.WEST}:
            for dx in range(min_dist, max_dist + 1):
                if p.x + dx < width and p.x + dx >= 0:
                    yield Pos(p.x + dx, p.y, Dir.EAST)
                if p.x - dx < width and p.x - dx >= 0:
                    yield Pos(p.x - dx, p.y, Dir.WEST)

    return neighbours


inp = [line.rstrip("\n") for line in stdin]


def normalize(n: int) -> int:
    return min(1, max(-1, n))


def d(a: Pos, b: Pos) -> int:
    ndx = normalize(b.x - a.x)
    ndy = normalize(b.y - a.y)
    total = 0
    if ndx != 0:
        for x in range(a.x + ndx, b.x + ndx, ndx):
            total += int(inp[a.y][x])
    elif ndy != 0:
        for y in range(a.y + ndy, b.y + ndy, ndy):
            total += int(inp[y][a.x])
    return total


goal = Pos(len(inp[0]) - 1, len(inp) - 1)

p1neighbours = make_neighbours(len(inp[0]), len(inp), 1, 3)
print(a_star(Pos(0, 0), goal, p1neighbours, goal.manhattan, d))
p2neighbours = make_neighbours(len(inp[0]), len(inp), 4, 10)
print(a_star(Pos(0, 0), goal, p2neighbours, goal.manhattan, d))