F - Looking for a Good Plot |
A rich guy wants to buy some land to build a house. He is a bit eccentric and wants his parcel to have rectangular shape, with the sides aligned with earth's meridians and parallels. Ideally, he would like a plot of land with a lake and, most importantly, with easy access by car.
He does not care very much about money, hence he wants to buy the largest rectangular plot of land available which has access by car and contains a lake or is crossed by a river. If he cannot find a plot with both water and a road, he prefers one with only access by car rather than one with only water. However, he will conform with a plot without either one if nothing better is available.
He has hired you to help him in his search.
Your program will receive a map of an area. The map will be oriented with the north at the top.
It will have to output the coordinates of the best plot available in the map, according to the following rules:
The input format is as follows:
An integer in a single line which indicates the number of maps that your program will have to process. Then, for each map there will be:
Character: | Meaning: |
# | Unavailable land |
- | Available land |
W | Water |
R | Road |
The output consists of one line for each map:
If at least a plot of land has been found, the program will output four integers
separated by one space: the x and y coordinates of the upper left corner of
the best plot and its width and height, in this order. If no suitable plot can be found,
the line will contain just the string "No good places.
".
Coordinates start at zero and grow southwards and eastwards.
3 4 4 ---- ###- -### ---- 10 10 ####R----- ####R----- ####R--WW- #####R--W- ----##R--- -----##RRR ------##-- ------WWWW ----WWWWWW ----WWWWWW 3 3 WWW WWW WWW
0 0 4 1 6 0 4 4 No good places.
OMP'10
Facultad de Informatica
Universidad de Murcia (SPAIN)