Problem A
Square Search
Many computer vision applications involve finding some target object in an image. Of course, this process is complicated by the presence of lots of other objects that don’t match the target. That’s what you have to deal with here. You will be given a square image defined by a two-dimensional array of ASCII characters. Your job is to find the largest square inside the image that’s made entirely of pound sign characters.
Input
Input consists of one image. The first line contains an integer $n$ ($1 \le n \le 2\, 000$) indicating both the number of rows and the number of columns in the image. The next $n$ lines each contain $n$ characters, where each is either a pound sign or a space.
Output
For each problem instance, output a line giving the row and column of the upper left corner of the largest square made entirely of pound signs. The location should be followed by the size of the square (length of a side). If there are ties, report the square that starts on the earliest row. If there are ties on the earliest row, report the square that starts the closest to the left. Rows are numbered starting from zero at the top row and columns are numbered starting at zero for the leftmost column.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 # # # # |
0 1 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
13 ### ## ###### ### # # # # ### #### ## ### ### ## # ## # ### ## #### #### ### # #### ###### ######## ## # ### ### ## # ######## # # # # # # ###### # #### # # # # |
7 4 3 |
