На уроке рисования
(Время: 2 сек. Память: 32 Мб Сложность: 59%)
В классе у Ани на уроке рисования учитель готовит большую новогоднюю стенгазету: каждый ученик должен принести один вырезанный фрагмент мозаики, чтобы потом все кусочки наклеить на общий плакат. Для этого учитель раздал детям необычные листы бумаги – каждый лист представляет собой прямоугольник из разноцветных клеток размером N × M клеток (цвет – натуральное число от 0 до 99). Каждый лист пронизан золотистыми косыми линиями, чтобы можно было отличить вертикальную и горизонтальную ориентации фрагментов.
Домашнее задание: из своего листа каждый ученик выбирает один прямоугольник любого размера и вырезает его строго по линиям клеток. Аня переживает, что кто-то может принести фрагмент, который окажется полностью таким же, как у неё: совпадёт не только размер вырезанного прямоугольника, но и вся раскраска – в каждой клетке на соответствующем месте будет тот же цвет. Аня хочет узнать, сколько различных прямоугольников вообще можно вырезать из данного листа.
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число T – количество уроков. Далее для каждого урока задаётся лист: в первой строке два натуральных числа N и M (1 ≤ N, M ≤ 100; 1 ≤ T ≤ 10), затем следуют N строк по M чисел в каждой – номера цветов клеток (от 0 до 99), разделённые пробелами.
Выходные данные
В выходной файл OUTPUT.TXT для каждого урока с новой строки выведите количество различных прямоугольников, которые можно вырезать из соответствующего листа.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2
2 2
1 9
9 9
3 4
2 0 2 6
2 0 2 6
2 0 2 6 | 7
27 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
