실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 512 MB |
과학자 현우의 실험실은 2D 격자 모양의 "셀"로 구성되어 있습니다. (거대한 체스판을 상상해 보세요). 초기에는 실험실이 비어져 있습니다.
현우는 ()개의 기계를 실험실에 하나씩 추가할 계획입니다. 번째 기계는 영역에 위치하며, 이 영역은 다른 모든 기기가 위치한 영역과 다릅니다. ().
'비효율적인' 기계는 기계가 수평이나 수직으로 정확히 세 개의 다른 기계와 인접해 있을 때를 말합니다. 비효율적인 기계들은 전력 소모가 증가합니다. 현우는 비효율적인 기계가 없을 때까지 기계를 계속 추가하려 합니다. 이 때 추가된 기기의 와 좌표가 반드시 범위 내에 위치할 필요는 없습니다.
범위 내의 각 에 대해, 초기 실험실에 번째 기계만 있다면 비효율적인 기계가 없을 때까지 현우가 추가로 설치해야 하는 최소한의 기계 수를 출력하세요.
첫 번째 줄에는 단일 정수 이 주어집니다. 다음 개의 줄 각각에는 두 개의 공백으로 구분된 정수가 적혀있고, 이는 기계가 위치한 셀의 좌표를 나타냅니다.
범위 내의 각 에 대해, 과학자 현우가 비효율적인 기계가 없을 때까지 추가해야 하는 기계의 최소 수를 개의 별도의 줄에 출력해야합니다.
9 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2 4 1
0 0 0 1 0 0 1 2 4
일 때, 현우는 (1,1)에 위치한 기계를 효율적으로 만들기 위해 (2,1)에 기계를 추가해야 합니다.
일 때, 현우가 할 수 있는 최선의 방법은 (2,0), (3,0), (2,-1), (2,3)에 기계를 추가하는 것입니다.
출처: USACO 2021 February Contest, Silver Problem 1. Comfortable Cows