백준 28130



from collections import deque


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

a = [0,0]

b = [0,0]

field = []

bd = 0



# (0,0)에서 (x,y)까지 가는데 걸리는 시간

def get_time(x, y):

    if x == 0:

        return y

    if y == m - 1:

        return x + y

    if x == n - 1:

        return n + 2 * m - 3 - y

    if y == 0:

        return 2 * n + 2 * m - 4 - x



# A가 (x,y)까지 이동하는데 걸린 시간t

# (0,0)에서 (x,y)까지 이동하는데 걸리는 시간 d

# (0,0)에서 B까지 이동하는데 걸리는 시간 bd

# 외곽 전체 길이 total

def calculate(x, y, t):

    d = get_time(x, y)

    track_len = 2 * n + 2 * m - 4

    return ((d - bd - t + track_len) % track_len)//2



def bfs():

    answer = 999999999

    dx = [-1,0,1,0]

    dy = [0,-1,0,1]

    visited = [[-1]*m for _ in range(n)]

    visited[a[0]][a[1]] = 0

    q = deque()

    q.append([a[0],a[1]])

    flag = False  # G에 둘러쌓여 갇힌 경우 체크

    while len(q):

        target = q.popleft()

        for i in range(4):

            x = target[0] + dx[i]

            y = target[1] + dy[i]

            if not (0 <= x < n and 0 <= y < m) or visited[x][y] >= 0 or field[x][y] == 'G':

                continue

            visited[x][y] = visited[target[0]][target[1]] + 1

            if x == 0 or x == n-1 or y == 0 or y == m-1:

                answer = min(answer, visited[x][y] + calculate(x, y, visited[x][y]))

                flag = True

                continue

            q.append([x, y])

    if not flag:  # 갇힌 경우

        print(-1)

    else:

        print(answer)



for _ in range(n):

    field.append(input())

for i in range(n):

    for j in range(m):

        if field[i][j] == 'A':

            a = [i,j]  # A위치 저장

        if field[i][j] == 'B':

            b = [i,j]  # B위치 저장


# 체스칸이라 가정하면 서로 다른 색깔에 위치하는 경우 만나는 것이 불가능

if (sum(a) + sum(b)) % 2:

    print(-1)

else:

    bd = get_time(b[0], b[1])  # 원점(0,0)에서 B까지 걸리는 시간

    bfs()



모르겠어용 ㅠ