문제 설명

m x n 크기인 사무실이 있습니다. 사무실에는 전염병에 걸린 직원이 있는데, 이 직원은 매일 상하좌우로 병을 퍼트려 다른 직원을 감염시킵니다. 단, 백신을 접종한 직원은 면역력이 있어 감염되지 않습니다.

예를 들어 2x4 크기 사무실에서, 병에 걸린 직원의 위치가 (1,4), (2,2)이고 백신을 맞은 직원의 위치가 (1,2)입니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기 까지는 이틀이 소요됩니다.

0일 573528139.32.png

1일

573528143.88.png

2일

573528147.73.png

사무실의 크기 m, n과 병에 걸린 직원의 위치 infests, 백신을 맞은 직원의 위치 vaccinateds가 매개변수로 주어집니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기까지 며칠이 걸리는지 return 하는 solution 함수를 완성해주세요.

제한사항
  • m과 n은 1 이상 300 이하인 자연수입니다.
  • infests

    의 길이는 1 이상

    m

    *

    n

    이하입니다.

    • infests의 원소는 [a, b] 형식이며, 1 ≤ a ≤ m, 1 ≤ b ≤ n입니다.
    • infests에는 같은 원소가 두 번 이상 들어있지 않습니다.
  • vaccinateds

    는 길이가 1 이상

    m

    *

    n

    이하입니다.

    • vaccinateds의 원소는 [a, b] 형식이며, 1 ≤ a ≤ m, 1 ≤ b ≤ n입니다.
    • vaccinateds에는 같은 원소가 두 번 이상 들어있지 않습니다.
  • 백신을 맞은 직원이 병에 걸린 경우는 주어지지 않습니다.
  • 병을 아무리 퍼트려도 백신을 맞은 직원을 제외한 모든 직원이 병에 감염될 수 없다면 -1을 리턴합니다.
입출력 예
m n infests vaccinateds result
2 4 [[1,4],[2,2]] [[1,2]] 2
2 3 [[2,2]] [[1,2],[2,1],[2,3]] -1
2 2 [[1, 1], [2, 2]] [[1, 2], [2, 1]] 0
입출력 예 설명

입출력 예 #1 문제의 예시와 같습니다.

입출력 예#2 573528150.21.png

전염병자의 근처가 백신 접종자로 막혀있어, 다른 직원에게 병이 도달하지 않습니다. 따라서 -1을 리턴합니다.

입출력 예#3

573533913.75.png

처음부터 모든 직원이 전염병을 앓고 있거나, 백신을 맞은 상태입니다. 따라서 0을 리턴합니다.