Woburn Challenge 2001 - Suicidal

Monday - Survivor

This is the first day of orientation and the frosh are already ready to isolate themselves. Therefore, they have been divided into 2 groups or "tribes" (and never the two shall meet). The two tribes are called the Keeg and the Dren. The orientation leaders have divided the barren wasteland that is the city of Waterloo into a giant grid; both tribes are to compete in a contest on this grid.

To begin the game, a random number will be drawn from a hat to represent the number of turns that will take place before the game is declared over. During each turn, each tribe will alternately position one of their students at one of the grid positions.

The goal is as follows. If you draw a straight line between students of the same tribe, it might turn out that 4 students are positioned so that they form a square (not necessarily parallel to the grid axis). On the last turn, the object of each tribe is to position a student of your tribe on the grid so that the square of largest possible area is formed using the students of that tribe on the grid as vertices of the square (the area is calculated from the coordinates of the square).

The tribe that forms that largest area wins and the losing tribe is kicked off the island (translation: kicked out of Waterloo engineering). Note that this event has been approved by Waterloo faculty as a much more efficient method of weeding out students from first year engineering.

Input

N (the size of the square grid, N ≤ 60; N = -1 signals the end of input)

The next N lines represent the grid itself at the beginning of the last turn: "*" means an unoccupied grid position, k represents a Keeg student, d represents a Dren student.

The next line of input is either "k" or "d". You must place a student of the appropriate tribe (depending on whether the input is "k" or "d") on a position on the grid to come up with the square of maximum area.

Output

The area of the largest such square that can be formed by the addition of the last student of the appropriate tribe.

Sample Input

4
*k**
**k*
*k*d
**d*
k
-1

Sample Output

2

NOTE: this is obtained by placing k at row 2, column 1; area = 2½ * 2½ = 2

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 05, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

1) Do all legal squares have a side that's either parallel to a side of the grid, OR 45 degrees? Or do really weird angles count too?

2) Is a square with just one "k" or "d" a square of size 1?

3) If 2) is no, then are we guaranteed a square can always be formed?

1) A square can be at any angle.

2/3) A single point counts as a square of size 0.