Sokkelo

from itertools import product
from math import inf
 
 
def I():
    return map(int, input().split())
 
 
def main():
    n, m = I()  # y,x
    sokStr = [input() for _ in range(n)]
 
    def findPerson(person):
        for i in range(n):
            a = sokStr[i].find(person)
            if a != -1:
                return a, i
    Ax, Ay = findPerson("A")
    Bx, By = findPerson("B")
    # Apath = []
    # Bpath = []
    sokkelo = [[1 if i == "#" else 0 for i in s] for s in sokStr]
    # wall is 1, A is 2, B is 3
 
    # def mark(x, y, side):
    #     if not sokkelo[y][x]:
    #         sokkelo[y][x] = side
    #         (Apath if side == 2 else Bpath).append((y, x))
    #         for a in (1, -1):
    #             if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
    #                 mark(x + a, y, side)
    #             if 1 <= y + a < n - 1:
    #                 mark(x, y + a, side)
    def isA(x, y):
        if 0 <= x < m and 0 <= y < n:
            return sokkelo[y][x] == 2
        return False
 
    mi = inf
 
    def ClosestA(x, y):
        d = 1
        while 1:
            for i in range(d):
                if isA(x + d - i, y + i):
                    return d
                if isA(x - d + i, y - i):
                    return d
                if isA(x + i, y - d + i):
                    return d
                if isA(x - i, y + d - i):
                    return d
            d += 1
            if d >= mi:
                return mi
 
    def updateMin(x, y):
        nonlocal mi
        e = ClosestA(x, y)
        if e < mi:
            mi = e
 
    def markA(x, y):
        if not sokkelo[y][x]:
            sokkelo[y][x] = 2
            for a in (1, -1):
                if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
                    markA(x + a, y)
                if 1 <= y + a < n - 1:
                    markA(x, y + a)
 
    def markB(x, y):
        if not sokkelo[y][x]:
            sokkelo[y][x] = 3
            updateMin(x, y)
            for a in (1, -1):
                if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
                    markB(x + a, y)
                if 1 <= y + a < n - 1:
                    markB(x, y + a)
    try:
        markA(Ax, Ay)  # Virhe on täällä, ei ole IndexError
    except:
        print(0)
        return
    if sokkelo[By][Bx] == 2:
        print(1)
        return
    markB(Bx, By)
 
    print(mi)
    return
 
 
if __name__ == "__main__":
    main()

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: WRONG ANSWER

Test 5

Group: 2

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED