АВТ ВоГУ - Задача 1554. Бубновый джокер

All your answers will be questioned

«Interstate 60»

У Арсения есть карта. И не одна, а целых 54. Не хватает только бубнового джокера. (Как же, вы не знаете, зачем нужен бубновый джокер?) Зато у него есть прямоугольный лист бумаги из тетрадки, из которого можно этого джокера вырезать.

Каждая клетка листа раскрашена в один из 26 цветов, а джокер должен представлять собой ромб, состоящий из клеток одного цвета. (Не обязательно красного; чёрный, или, скажем, синий бубновый джокер никого не смутит).

В данной задаче ромбом с центром в клетке (r₀,c₀) (r — номер строки, c — номер столбца) радиуса R называется множество клеток (r_i,c_i), удовлетворяющих неравенству |r_i-r₀|+|c_i-c₀|≤R.

Конечно, б'ольший джокер полезнее в игре, так что Арсений хочет вырезать из бумаги самый большой ромб, состоящий из клеток одинакового цвета. Напишите программу, которая ему в этом поможет.

Входные данные

В первой строке входного файла заданы через пробел два числа m и n (1≤m,n≤500) — размеры прямоугольника (в клетках). Каждая из m последующих строк содержит по n прописных латинских букв, каждая латинская буква соответствует определённому цвету. Вторая строка во входном файле соответствует первой строке прямоугольника, (m+1)-я строка соответствует m-й строке прямоугольника.

Выходные данные

Выведите в выходной файл три числа r₀, c₀ и R через пробел — номер строки и номер столбца центра, а также радиус ромба наибольшего размера. Если таких ромбов несколько, выведите ромб с наименьшим номером строки. В случае неоднозначности, выведите ромб с наименьшим номером столбца.

Выведенные числа также должны удовлетворять неравенствам:

1+R≤r₀≤m-R,1+R≤c₀≤n-R, то есть ромб для джокера должен целиком лежать в прямоугольнике.

Пример

Входные данные

4 5
ABAAA
AAAAA
AAAAA
AAAAA

Выходные данные

2 3 1

Дистанционный практикум по программированию

1554. Бубновый джокер