Sokkelo

# 2022 loppu C

n, m = map(int, input().split())

rivit = [input() for _ in range(n)]

# let's try generating outlines of walls

#    3
#   2 0
#    1


def find_letter(letter: str):
    for i in range(n):
        a = rivit[i].find(letter)
        if a != -1:
            return a, i
    raise TypeError()


A_pos = find_letter("A")
B_pos = find_letter("B")


def is_path(x: int, y: int):
    return rivit[y][x] != "#"


def advance(x: int, y: int, d: int):
    d %= 4
    if d == 0:
        return x + 1, y
    elif d == 1:
        return x, y + 1
    elif d == 2:
        return x - 1, y
    elif d == 3:
        return x, y - 1
    raise TypeError()


class IsSurrounded(Exception):
    ...


class IsConnected(Exception):
    ...


def step_outline(x: int, y: int, d: int):
    for i in range(4):
        a, b = advance(x, y, d + i - 1)
        if is_path(a, b):
            return a, b, d + i - 1
    raise IsSurrounded()


def cast_ray(x: int, y: int, d: int):
    while 1:
        a, b = advance(x, y, d)
        if is_path(a, b):
            x, y = a, b
        else:
            return x, y


def seek_advance(x: int, y: int, tx: int, ty: int):
    "returns new position, direction"
    if abs(x - tx) > abs(y - ty):
        if x > tx:
            return x - 1, y, 2
        else:
            return x + 1, y, 0
    else:
        if y > ty:
            return x, y - 1, 3
        else:
            return x, y + 1, 1


def seek_ray(x: int, y: int, tx: int, ty: int):
    while 1:
        a, b, d = seek_advance(x, y, tx, ty)
        if a == tx and b == ty:
            raise IsConnected()
        if is_path(a, b):
            x, y = a, b
        else:
            return x, y, d


def generate_outline(x: int, y: int, d: int):
    """returns the points of the outline, whether it is an interior outline, and a point at the opposite end (granted d is 1).
    \n tracing an outline must start at a point where there is a wall at the d-1 direction"""
    a, b, d = step_outline(x, y, d)
    start_d = d
    points: "list[tuple[int,int]]" = [(a, b)]
    opposite_x = x  # largest x coordinate with y as the y parameter. currently works only if d parameter is 1
    while 1:
        a, b, d = step_outline(*points[-1], d)
        if (a, b) == points[0] and d % 4 == start_d % 4:
            assert(abs(d - start_d) == 4)
            # d - start_d == 4 means this is inside, == -4 means this is outside
            is_interior = (d - start_d == 4)
            return points, is_interior, (opposite_x, y)
        points.append((a, b))
        if b == y and opposite_x < a:
            opposite_x = a


def get_bound(x: int, y: int):
    "get the interior outline (x,y) is inside of"
    try:
        step_outline(x, y, 0)
    except IsSurrounded:
        return [(x, y)]
    a, b = x, y
    while 1:
        a, b = cast_ray(a, b, 0)
        points, is_interior, opposite = generate_outline(a, b, 1)
        if is_interior:
            return points
        a, b = opposite


def is_inside(x: int, y: int, outline: "list[tuple[int,int]]"):
    "is the point x,y inside the area marked by the outline?"
    if (x, y) in outline:
        return True
    l = len(outline)
    if l == 1:
        return False
    downs = 0
    for i in range(l):
        if outline[i][1] == y and outline[i][0] < x:
            downs += outline[i - 1][1] - outline[(i + 1) % l][1]
    return downs != 0


import itertools


def manhattan(a: "tuple[int,int]", b: "tuple[int,int]"):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def manhattan2(ax: int, ay: int, bx: int, by: int):
    return abs(ax - bx) + abs(ay - by)


def outline_distance(a: "list[tuple[int,int]]", b: "list[tuple[int,int]]"):
    return min(manhattan(c, d) for c, d in itertools.product(a, b))


def closest_in_outline(x: int, y: int, outline: "list[tuple[int,int]]"):
    def key(k):
        return manhattan2(x, y, *k)
    return min(outline, key=key)


def get_bound_seek(x: int, y: int, tx: int, ty: int):
    "get the outline closest to (tx,ty) that can be reached from (x,y)"
    try:
        step_outline(x, y, 0)
    except IsSurrounded:
        return [(x, y)]
    a, b = x, y
    while 1:
        a, b, d = seek_ray(a, b, tx, ty)
        outline, is_interior, opposite = generate_outline(a, b, d + 1)
        is_in = is_inside(tx, ty, outline)
        # print(a, b, d, tx, ty, is_interior, is_in, outline)
        if is_interior and not is_in:
            return outline
        elif is_in and not is_interior:
            return outline
        a, b = closest_in_outline(tx, ty, outline)


try:
    A_bound = get_bound_seek(*A_pos, *B_pos)
    B_bound = get_bound_seek(*B_pos, *A_pos)
except IsConnected:
    print(1)
else:
    print(outline_distance(A_bound, B_bound))

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: ACCEPTED

Test 5

Group: 2

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 1, 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED