이번 문제는 BFS를 통해 해결하였다. 세명의 악당의 위치를 기준으로 BFS를 통해 모든 좌표로의 거리를 구하고, 모든 좌표를 순회하며 세명의 악당으로부터의 거리가 모두 갱신되어 있을 때의 셋 중의 최댓값을 구하고, 이를 결과 변수와 비교하여 더 작은 경우 결과변수를 갱신하고, 같을 경우에는 카운팅 변수를 증가시키도록 하였다.

Code

from collections import deque
r, c = map(int, input().split())
grid = [list(str(input())) for _ in range(r)]
villain = [list(map(int, input().split())) for _ in range(3)]
dists = [[[1e9 for _ in range(3)] for _ in range(c)] for _ in range(r)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def bfs(idx, sy, sx):
    q = deque()
    q.append((sy-1, sx-1, 0))
    dists[sy-1][sx-1][idx] = 0
    while q:
        y, x, dist = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == '0' and dists[ny][nx][idx] == 1e9:
                dists[ny][nx][idx] = dist+1
                q.append((ny, nx, dist+1))
for idx in range(3):
    bfs(idx, villain[idx][0], villain[idx][1])
answer = 1e9
cnt = 0
for i in range(r):
    for j in range(c):
        if dists[i][j][0] == 1e9 or dists[i][j][1] == 1e9 or dists[i][j][2] == 1e9:
            continue
        ans = max(dists[i][j])
        if answer > ans:
            answer = ans
            cnt = 1
        elif answer == ans:
            cnt += 1
if answer == 1e9:
    print(-1)
else:
    print(answer)
    print(cnt)