정올 미술 입시학원은 정올 컴퓨터학원이 확장하여 생긴 새로운 학원이다. 정올 컴퓨터 학원처럼 좋은 성적을 많이 낸 정올 미술 입시학원도 컴퓨터 학원에 밀리지 않을 만큼 학생수가 아주 많아지게 되었다.

정올 미술 입시학원을 총괄하여 책임지고 있는 빛쌤은, 학생들에게 그림의 샘플을 주고 따라 그리게 하는데, 그 샘플은 N행 M열의 격자로 나타낼 수 있는 캔버스에 A부터 Z까지의 26가지의 색깔이 칠해져 있다.

그림을 따라 그리는 학생은 붓에 물감을 묻혀서, 한 획으로 “상하좌우로 연결된” 모든 칸을 색칠할 수 있다.

한 칸에 색깔을 두 번 이상 덮어씌우는 것은 불가능하다. 예를 들어 샘플이 3x3 크기이고, 아래와 같다고 가정해 보자.

AAB

BBA

BBB

이걸 따라 그리는 빛쌤의 학생은 최소 4획으로 그림을 완성할 수 있다.

... ..B AAB AAB AAB

... -> ... -> ... -> BB. -> BBA

... ... ... BBB BBB

4획보다 적은 횟수로 그림을 완성하는 것은 불가능하다.

학생이 너무 많아지자, 모든 학생들이 같은 샘플을 그리게 하는 것이 조금 단조로웠다고 생각한 빛쌤은(여러분도 알다시피, 미술 입시학원은 학생들의 작품을 학원 바깥에 전시하는 것이 일반적이므로, 되도록이면 다른 작품을 걸어놓는 것이 좋다,) Q명의 학생들에게 전체 샘플의 각각 다른 일부분만을 그리도록 하려고 한다.

즉, Q개의 “부분 샘플”이 나오게 되는데, 하나의 부분 샘플은 전체 샘플의 x₁행부터 x₂행까지, y₁열부터 y₂행까지의 부분 직사각형이다.

빛쌤은 학생들이 많아지자, 학생들이 붓에 물감을 묻히는 횟수를 최대한 줄여야겠다고 생각하고, 각 부분 샘플별로 그림을 완성하는데 드는 최소 획수를 구하려고 한다.

이를 구하는 프로그램을 작성하라.

#4716 upload 9 done 2 how_to_reg 2

정올 미술 입시학원 timer 3s memory 512MB

#4716

정올 미술 입시학원 3s 512MB