AIOC Banner

Problem: Landmark

Want to try solving this problem? You can submit your code online if you log in or register.


Landmark

Input File: landin.txt
Output File: landout.txt
Time Limit: 1 second

You are mayor of the city, and it's almost election time. It is clear to you that the only way to get re-elected is to construct a huge landmark in the centre of the city. Perhaps a bird park, since the polls show that most people associate colourful birds with happiness.

Trouble is, the city is already full of buildings and there is no free space. To build your bird park, you will need to knock some buildings down.

The city is divided into square blocks. Each block is either commercial or residential. You cannot knock down any commercial buildings, since the businesses will get angry and stop donating to your campaign fund. You therefore need to find a suitable residential area that can be knocked down so that you can build your new bird park and make your citizens happier people.

The bird park will be rectangular in shape. Due to building regulations it may only be one block wide, though it can be as long as you like. The bird park may be placed either horizontally or vertically in the city.

Two city maps of 5 x 6 blocks are illustrated below. In each map the commercial blocks are coloured black, and the blocks used to create the largest possible bird park are marked with the letter B. In the first map, the largest possible bird park is horizontal and four blocks in length, whereas in the second map it is vertical and three blocks in length.

You must write a program that can read in a city map and find the location where you can build the largest bird park possible, thereby securing your re-election.

Input

The input file will describe a single city map. The first line of input will contain the two integers r and c separated by a single space, representing the number of rows and columns in this map respectively. The rows are numbered 1,2,...,r from top to bottom and the columns are numbered 1,2,...,c from left to right. You are guaranteed that 1 <= r,c <= 1000.

Following this will be r lines describing rows 1,...,r in order. Each of these lines will contain precisely c characters, where the cth character of the rth line represents the city block in column c, row r. Each of these characters will be a period (.) or a hash (#), where a period represents a residential block and a hash represents a commercial block.

You are guaranteed that the map will contain at least one residential block.

Output

You must write a single line as output, giving the coordinates of each end of your bird park. This line must be of the form r1 c1 r2 c2, where the bird park starts at the block in row r1, column c1 and ends at the block in row r2, column c2.

You may output the start and end blocks in either order. If there is more than one best location for the bird park, you may output any one of these best locations.

Sample Input 1

5 6
##.#..
...#..
#.#.#.
#....#
.##...

Sample Output 1

4 2 4 5

Sample Input 2

5 6
.##.#.
..#..#
#.##.#
.##..#
.#.##.

Sample Output 2

2 5 4 5

Scoring

The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019, 11:29pm AEST