eolymp
bolt
Try our new interface for solving problems
Məsələlər

Гербарий

Гербарий

Школьнику задали собрать гербарий, в котором не менее \textbf{K} листьев разных типов деревьев. В распоряжении школьника роща, которая разделена на \textbf{N} рядов, в каждом из которых по \textbf{M} квадратных участков одного размера. На каждом участке растут деревья одного типа. Школьник решил собрать гербарий на фрагменте рощи квадратной формы. При этом он хочет знать минимальное количество участков, которые требуется обойти. Зная, на каком участке растут какие деревья, требуется написать программу, которая поможет определить минимальный фрагмент рощи квадратной формы, позволяющий собрать гербарий, и подсчитать \textbf{количество участков} в данном фрагменте. \textbf{Примечание}: школьник обходит \textbf{все} участки квадратного фрагмента рощи. \InputFile Первая строка содержит три целых числа \textbf{N}, \textbf{M}, \textbf{K} разделенных пробелами (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{100}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10000}). Следующие \textbf{N} строк содержат по \textbf{M} неотрицательных целых чисел, разделенных пробелами. Каждое число характеризует тип деревьев, которые растет в \textbf{i}-ом ряду на \textbf{j}-ом месте (\textbf{1} ≤ \textbf{i} ≤ \textbf{N}, \textbf{1} ≤ \textbf{j} ≤ \textbf{M}). Значение номера типа дерева не превышает \textbf{10^9}. \OutputFile Выходной файл должен содержать одно целое число -- количество участков в минимальном фрагменте рощи квадратной формы, который достаточно обойти школьнику, чтобы собрать гербарий. Гарантируется, что есть хотя бы один квадратный фрагмент рощи, который подходит школьнику.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 16 MiB
Giriş verilənləri #1
5 5 3
1 2 2 2 4
1 2 2 2 2
1 1 2 2 2
2 1 2 2 2
1 1 2 3 3
Çıxış verilənləri #1
9
Mənbə Региональная олимпиада по программированию, СибГИУ, 2011