Раскраска
PAINTER
Описание
Как-то раз маленькому мальчику Пете родители ко дню рождения подарили детский набор, состоящий из раскраски и K цветных карандашей (все карандаши разноцветные). Раскраска представляет собой лист бумаги шириной M см и длиной N см. Этот лист условными линиями разбит ровно на N
Установлены следующие правила раскрашивания:
раскраска считается раскрашенной, если все клетки закрашены;
раскрашивать можно только данными K карандашами (цветами);
каждая клетка закрашивается полностью одним из K цветов.
Задача
Петя считает полностью раскрашенную раскраску «красивой», если в ней можно выделить одноцветный прямоугольник со сторонами больше 1 см. Пете стало интересно, сколько различных вариантов «красивой» раскраски можно получить? Напишите программу PAINTER, с помощью которой мальчик сможет найти ответ на этот вопрос
Два варианта полностью раскрашенной раскраски считаются различными, если существует такая клетка в первом варианте, цвет которой отличается от цвета соответствующей (в той же строке и том же столбце) клетки во втором варианте, причем поворачивать раскраску нельзя.
На рисунке выше изображен пример теста. Ответом на этот тест будет число 4. Так как четыре «красивых» варианта раскраски – это рисунки с номерами 2,3,4,5. Во всех этих рисунках, можно выделить одноцветный квадрат со стороной 2 см (в рисунках 2 и 5 одного цвета, а в рисунках 3 и 4 – другого цвета), рисунок 6 не является красивой раскраской.
Формат входных данных
В первой строке входного файла PAINTER.IN содержаться три числа N, M и K (1<=N,M<=50, 2<=K<=10, 2<=N×M×K<=100), разделенные пробелами. Следующие N строк по M чисел в каждой описывают каждую клетку раскраски целым числом от 0 до K, где 0 - клетка не закрашена, в противном случае - цвет закрашенной клетки. Числа в каждой строке разделены одним пробелом
Формат выходных данных
Выходной файл PAINTER.OUT должен содержать одно число – количество различных «красивых» вариантов раскраски
Например:
PAINTER.IN
2 3 2
2 0 0
0 0 1
PAINTER.OUT
4