always turns left (13 steps)
trail (32 Steps)
Sally the Snail lives on an 8x8 grid which contains some obstructions (shown below as black squares). Sally always moves as far as she can in a straight line. When she reaches an obstruction or the edge of the board, she turns either right or left. When she encounters a square she has already visited, she stops.
|
|
| SubTaskA : Trail when Sally always turns left (13 steps) |
SubTask B : The longest trail (32 Steps) |
Sally always starts at square A1, and begins moving in a downward direction. You will be given the location of all the black squares on the grid, and your task is to find out how many steps Sally can take before getting blocked. In subtask A, Sally always turns to her left, and in subtask B, Sally turns either left or right to maximise the length of the trail.
The diagrams show an example grid with three black squares (at A6, E2 and F5). The trails for each subtask are also shown. In subtask A, Sally moves from A1 down to A5, where she turns to her left and heads off to E5. From here, she turns left to square E3, and again turns left to finish at B3. She has taken 13 steps.
In subtask B, Sally wants the longest route, which is shown in the diagram to have 32 steps.
The input is an integer n, (1 <= n <= 32), the number of black squares, followed by the positions of the n squares in the form of Xn, where X, (A X H), is the column, and n, (1 n 8) is the row.
Note that there will be no black squares on A1 or A2.
The output will be the number of steps for subtask A, followed by the number of steps for subtask B.
Input
3 A6 E2 F5
Output
13 32
Input
6 A6 C1 C3 D4 E3 B7
Output
21 22
Here are the diagrams for example 2.
 |
 |
| SubTaskA : Trail when Sally always turns left (21 steps) |
SubTask B : The longest trail (22 Steps) |