504. Square Palindrome
Time limit per test: 0.25
Memory limit: 262144
Andrew has just made a breakthrough in computer science: he realized how
to quickly find the largest palindrome square on a given rectangle of letters.
Can you do the same?
A square consisting of n
rows of n
letters each is a
of size n
if each row and each column of this square
is a palindrome string. A string is a palindrome string
if its first
letter is the same as its last letter, its second letter is the
same as its next-to-last letter, and so on.
The first line of the input file contains two integers h
(1 ≤ h
≤ 700) — the height and width of the
given rectangle of letters.
The next h
lines contain w
lowercase English letters each —
the given rectangle of letters itself.
Output the coordinates of the largest palindrome square that is a part of the
given rectangle of letters. Output four integers: the first row of the
the first column of the square, the last row of the square, the last column
of the square. The rows are numbered from 1 to h
, the columns are numbered
from 1 to w
. If there are several solutions, output any.
1 2 4 5