На разборе задач одного из контестов петрозаводских сборов Вова и Саша поспорили, кто из них сможет найти за 300 минут в матрице размера N × M, состоящей из строчных латинских букв,
пару одинаковых квадратов наибольшего размера. Квадраты могут накладываться друг
на друга, но не могут совпадать. Кто нашёл пару большего размера, тот и выиграл.
Мимо проходил Петя, посмотрел на матрицу, сказал, что оптимальная пара квадратов
имеет сторону K, и пошёл дальше. Вова и Саша до сих пор пытаются найти этот ответ.
Может быть, вы скажете, какую пару квадратов имел в виду Петя?
Исходные данные
В первой строке через пробел даны два целых числа N и M. 1 ≤ N, M ≤ 500.
В следующих N строках по M символов в каждой строке приведена матрица из строчных
латинских букв.
Результат
В первой строке выведите целое число K, которое сказал Петя. В следующих двух строках выведите координаты
левой верхней клетки каждого из квадратов. Если существует более одной пары одинаковых квадратов
наибольшего размера, то можно вывести любую из них. Вы можете считать, что левая верхняя клетка матрицы имеет координаты (1, 1), правая нижняя — координаты (N, M). Если Петя сказал, что в матрице
не существует пары одинаковых квадратов, выведите единственное число 0.
Пример
исходные данные | результат |
---|
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
| 3
1 1
3 3
|
Автор задачи: Владимир Яковлев
Источник задачи: XI Чемпионат УрГУ по программированию, 7 октября, 2006