ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Одинаковые квадраты

Ограничение времени: 2.0 секунды
Ограничение памяти: 128 МБ
На разборе задач одного из контестов петрозаводских сборов Вова и Саша поспорили, кто из них сможет найти за 300 минут в матрице размера N × M, состоящей из строчных латинских букв, пару одинаковых квадратов наибольшего размера. Квадраты могут накладываться друг на друга, но не могут совпадать. Кто нашёл пару большего размера, тот и выиграл. Мимо проходил Петя, посмотрел на матрицу, сказал, что оптимальная пара квадратов имеет сторону K, и пошёл дальше. Вова и Саша до сих пор пытаются найти этот ответ. Может быть, вы скажете, какую пару квадратов имел в виду Петя?

Исходные данные

В первой строке через пробел даны два целых числа N и M. 1 ≤ NM ≤ 500. В следующих N строках по M символов в каждой строке приведена матрица из строчных латинских букв.

Результат

В первой строке выведите целое число K, которое сказал Петя. В следующих двух строках выведите координаты левой верхней клетки каждого из квадратов. Если существует более одной пары одинаковых квадратов наибольшего размера, то можно вывести любую из них. Вы можете считать, что левая верхняя клетка матрицы имеет координаты (1, 1), правая нижняя — координаты (NM). Если Петя сказал, что в матрице не существует пары одинаковых квадратов, выведите единственное число 0.

Пример

исходные данныерезультат
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
3
1 1
3 3
Автор задачи: Владимир Яковлев
Источник задачи: XI Чемпионат УрГУ по программированию, 7 октября, 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1486. Одинаковые квадраты