문제
정올 미술 입시학원은 정올 컴퓨터학원이 확장하여 생긴 새로운 학원이다. 정올 컴퓨터 학원처럼 좋은 성적을 많이 낸 정올 미술 입시학원도 컴퓨터 학원에 밀리지 않을 만큼 학생수가 아주 많아지게 되었다.
정올 미술 입시학원을 총괄하여 책임지고 있는 빛쌤은, 학생들에게 그림의 샘플을 주고 따라 그리게 하는데, 그 샘플은 N행 M열의 격자로 나타낼 수 있는 캔버스에 A부터 Z까지의 26가지의 색깔이 칠해져 있다.
그림을 따라 그리는 학생은 붓에 물감을 묻혀서, 한 획으로 “상하좌우로 연결된” 모든 칸을 색칠할 수 있다.
한 칸에 색깔을 두 번 이상 덮어씌우는 것은 불가능하다. 예를 들어 샘플이 3x3 크기이고, 아래와 같다고 가정해 보자.
AAB
BBA
BBB
이걸 따라 그리는 빛쌤의 학생은 최소 4획으로 그림을 완성할 수 있다.
... ..B AAB AAB AAB
... -> ... -> ... -> BB. -> BBA
... ... ... BBB BBB
4획보다 적은 횟수로 그림을 완성하는 것은 불가능하다.
학생이 너무 많아지자, 모든 학생들이 같은 샘플을 그리게 하는 것이 조금 단조로웠다고 생각한 빛쌤은(여러분도 알다시피, 미술 입시학원은 학생들의 작품을 학원 바깥에 전시하는 것이 일반적이므로, 되도록이면 다른 작품을 걸어놓는 것이 좋다,) Q명의 학생들에게 전체 샘플의 각각 다른 일부분만을 그리도록 하려고 한다.
즉, Q개의 “부분 샘플”이 나오게 되는데, 하나의 부분 샘플은 전체 샘플의 x1행부터 x2행까지, y1열부터 y2행까지의 부분 직사각형이다.
빛쌤은 학생들이 많아지자, 학생들이 붓에 물감을 묻히는 횟수를 최대한 줄여야겠다고 생각하고, 각 부분 샘플별로 그림을 완성하는데 드는 최소 획수를 구하려고 한다.
이를 구하는 프로그램을 작성하라.
입력
첫 줄에 N, M, Q가 주어진다.
다음 N행 M열에 걸쳐, 전체 샘플이 공백 없이 주어진다. 각 칸은 ‘A’부터 ‘Z’까지의 알파벳 대문자 중 하나이다.
다음 Q줄에 걸쳐, 부분 샘플의 크기를 나타내는 x1, y1, x2, y2가 공백을 사이에 두고 주어진다.
[제약형식]
1 ≤ N, M, Q ≤ 1,000 이며, 모든 학생들의 부분 샘플에 있어서, 1≤x1≤x2≤N, 1≤y1≤y2≤M을 만족한다. 캔버스의 알파벳을 제외한 모든 입력값은 정수이다.
출력
각 Q명의 학생들에 대해, 한 줄에 필요한 최소 획수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10 점 | N,M ≤ 50 |
| #2 | 15점 | 같은 색깔로 연결된 어떤 칸의 집합도 싸이클이 존재하지 않는다. 보다 엄밀하게 말하자면, 같은 색깔의 칸 c1, c2, c3,… ck를 뽑았을 때, k>2이면서, 모든 k-1이하의 i값에 대해서 ci와 ci+1이 인접하고, ck가 c1과 인접한 경우는 없다. 아래 붉은 부분은 싸이클의 예시이다. AAB BBA BBB |
| #3 | 15점 | 같은 색깔로 연결된 어떤 칸의 집합도 2x2의 정사각형 내부에 들어간다. 해당 예시는 붉은 부분 때문에 이 부분문제에 속하지 않는다. AAB BBA BBB |
| #4 | 15점 | 같은 색깔로 연결된 어떤 칸도 3x3의 정사각형에 맞아 들어간다. 위 예시는 이 부분문제에 속한다. |
| #5 | 45점 | 추가 제약 조건 없음. |
예제1
4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8
6
3
2
1
4
1
3
2
2