There is chaos at the airports! A volcano has just erupted, causing a cloud of ash that is spreading and preventing air traffic. The governments of the affected countries are very worried and want to know when the ash cloud will hit their airports.In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 21st
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #10 exercise sheet]
(this problem is an adaptation from an ONI'2010 qualification problem)
There is chaos at the airports! A volcano has just erupted, causing a cloud of ash that is spreading and preventing air traffic. The governments of the affected countries are very worried and want to know when the ash cloud will hit their airports.
They has access to a satellite map detailing the current situation. The map is a grid divided into smaller cells. Given the situation under analysis, only three types of cells are distinguished: cloud (indicating that this sector of the map is currently covered by an ash cloud), airport (letter 'A', indicating that this sector of the map contains an airport) and all others (which currently have neither a cloud nor an airport). An example of a map is shown in the following figure:
As time goes by, the situation gets worse. In fact, for every day that passes, the cloud expands by one cell horizontally and vertically. In other words, at the end of a day, all the cells that were adjacent (vertically or horizontally) to a cell with a cloud will also contain clouds. To figure below illustrates the evolution of the situation after two days:
|
 |
 |
|
 |
| Today | Tomorrow (1 day after) | 2 days after |
In order to properly prepare contingency plans, the governments need to know two things: how many days will pass before at least one airport is covered by the ash cloud, and in how many days from now will all the airports be covered by the ash cloud. You have to help!
Given a grid of R rows by C columns showing the current position of the cloud and the airports, your task is to find out Nmin, the number of days until the first airport is under the ash cloud, and Nmax, the number of days until all the airports are covered in ash.
The first line of the input contains two integers R and C, separated by a space, indicating respectively the number of rows and columns of the map.
This is followed by exactly R lines, each containing exactly C characters, describing the map. Each character can be:
There is always at least one cell with a cloud and one cell with an airport, but you shouldn't assume anything else about the other cells.
The output should be a line containing two integers Nmin and Nmax, separated by a single space, indicating respectively the number of days until a first airport is covered by the cloud and the number of days until all airports are covered.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ R, C ≤ 250 | Number of rows and columns |
| Example Input | Example Output |
7 8 ..#...## .##..... ###.A..A .#...... .#....A. ...A.... ........ |
2 4 |
Explanation of Example Input
The input corresponds to the figure in the problem statement.
Is takes two days for the cloud to to reach the first airport and four days for all airports being covered.