Spreading
Coddy의 코딩 문제 코스 레슨 — 32개 중 31번째.
챌린지
어려움한 동네에서 모든 이웃은 회색으로 칠해진 집의 색을 따라 합니다. 그래서 어떤 집들이 회색으로 칠해진 날, 그 집들과 가로 및 세로로 인접한 모든 이웃은 자신의 집도 똑같이 칠하기로 결정합니다. 그 작업에는 한 달이 걸립니다. 그 후, 그들과 가로 및 세로로 인접한 집들이 똑같은 결정을 내리고, 그들도 한 달이 걸리는 식으로 계속됩니다.
####X ##XXX #XXXX XXXXX
##X## #XXXX XXXXX XXXXX
##### ##X## #XXXX XXXXX
Mo.1 Mo.2 Mo.3 Mo.4
보시다시피, 처음에는 두 채의 집만 회색으로 칠해져 있습니다 ([1,5]와 [2,3]). 한 달 후에는 이미 칠해진 집들의 위, 아래, 오른쪽, 왼쪽에 있는 집들을 포함하여 8채의 집이 회색으로 칠해집니다. 두 달 후에는 13채의 집이 회색으로 칠해지고, 세 달 후에는 동네의 모든 집이 회색으로 칠해집니다.
입력으로 동네의 높이와 너비를 나타내는 두 자연수 H와 W가 주어집니다. 다음 줄에는 회색으로 칠해져야 하는 집의 총 개수를 나타내는 자연수 N이 주어집니다. 그다음 줄에는 자연수 M이 주어지고, 이어지는 M개의 줄에는 이미 회색으로 칠해진 집들의 위치를 나타내는 두 자연수 X와 Y가 주어집니다.
총 N채의 집이 회색으로 칠해지는 데 몇 달이 걸리는지 출력하세요 (처음에 이미 칠해져 있던 집들을 포함합니다).
Input
3 5
7
2
1 5
2 3
Output
1
Explanation #1: 위 본문에서 제시된 예시입니다. 동네의 높이는 3이고 너비는 5입니다. 총 7채의 집이 회색으로 칠해지는 데 몇 달이 걸리는지 출력해야 합니다. 이미 회색으로 칠해진 집은 [1, 5]와 [2, 3] 위치에 2채가 있습니다. 따라서 총 7채의 집이 회색으로 칠해지는 데는 한 달이 걸립니다.
직접 해보기
#include <stdio.h>
int main() {
// 여기에 코드를 작성하세요
return 0;
}
코딩 문제의 모든 레슨
1Course Introduction
Introduction