바이러스 백신

N×N 크기의 도시에 병원과 벽을 제외한 모든 지역에 바이러스가 생겼습니다. 비용상의 문제로 모든 병원에서 백신을 공급할 수는 없어, M개의 병원을 적절히 골라 최대한 빨리 바이러스를 없애려고 합니다.

M개의 병원을 고르게 되면, 골라진 병원들을 시작으로 매 초마다 상하좌우로 인접한 지역 중 벽을 제외한 지역에 백신이 공급되기 때문에 그 자리에 있던 바이러스는 사라지게 됩니다.

예를 들어 위의 예에서 M=3 일때 다음과 같이 병원을 고른 경우를 생각해봅시다.