eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Раскрась по буквам

Раскрась по буквам

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Беси недавно получила набор красок. Холст может быть представлен как n * m прямоугольник из ячеек, где строки пронумерованы 1..n сверху вниз, а столбцы пронумерованы 1..m слева направо. Покрашенная ячейка представляется большой буквой от 'A' до 'Z'. Изначально все ячейки не раскрашены, и ячейка не может краситься более одного раза.

У Беси есть желаемый цвет для каждой ячейки. Она может красить множество ячеек одним касанием, если это множество образуем связную компоненту, то есть что любая её ячейка достижима из любой другой через последовательность соседних ячеек. Две ячейки называются соседними, если они имеют общую сторону.

Например, рассмотрим холст 3 * 3:

AAB
BBA
BBB

Он может быть раскрашен за 4 касания так:

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

Невозможно его раскрасить менее чем за 4 касания.

Будучи авангардисткой, Беси намерена покрасить только подрегион холста. Сейчас она рассматривает q кандидатов, каждый из которых представляется четырьмя целыми числами x[1], y[1], x[2], y[2]. Это означает, подпрямоугольник состоит из всех ячеек со строками в диапазоне от x[1] до x[2] включительно, и колонками в диапазоне от y[1] до y[2] включительно.

Для каждого такого прямоугольника какое требуется минимальное количество касаний, чтобы раскрасить каждую из ячеек этого прямоугольника желаемым цветом, оставляя не закрашенными все ячейки вне этого подпрямоугольника. Заметим, Беси ничего не красит реально, поэтому ответы для каждого кандидата независимы.

Входные данные

Первая строка ввода содержит n, m (1n, m1000), q (1q1000).

Каждая из последующих n строк содержит строку из m больших букв, представляющих желаемый цвет каждой строки холста.

Каждая из следующих q строк содержит четыре целых числа x[1], y[1], x[2], y[2], представляющих подпрямоугольник (1x[1]x[2]n, 1y[1]y[2]m).

Выходные данные

Для каждого из q запросов выведите ответ в отдельной строке.

Пример

Первый кандидат - на весь холст, его можно раскрасить за 6 касаний.

Второй кандидат - подпрямоугольник с желаемыми цветами

ABBA

и может быть раскрашен за 3 касания. Заметим, что хотя ячейки (3, 5) и (3, 8) могут быть раскрашены в цвет A одним касанием на целом холсте, они не могут быть так раскрашены в указанном прямоугольнике.

Пример

Входные данные #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
Выходные данные #1
6
3
2
1
4
1
3
2
2
Источник 2021 USACO Январь, Платина