406757: GYM102535 N Connect Floors

Your organization's arch nemesis, the Mysterious Criminal Absconder, is hiding on the very top floor of your headquarters! You know because you were just passing by the ground floor when you heard a distinct evil "I'm hiding in my enemy's HQ" cackle from the top of the building. It is now your job to get from the ground floor to the top floor and capture him.

The Absconder has also hacked all the high-security doors and elevators such that they can't open anymore. The only solution now is to cut normal doors into the walls with your high-power laser, whose battery is currently running dangerously low, and take the stairs. (Really, a rookie move; all spies know that you should have at least five spare lasers on you.)

Furthermore, taking the stairs, to say the least, is not so simple in your organization's headquarters. The layout of the entire building is designed to be confusing to those unfamiliar with it; each floor can be of different sizes, staircases are put in random places and only let you climb to certain floors. One staircase, for example, might connect only the ground floor, the 3rd floor, and the 10th floor, while another may connect only the fifth floor and the sixth.

Fortunately, as a responsible member of the organization, you have the floor plans of the headquarters $$$F$$$ burned into your brain. You remember that the headquarters has $$$n$$$ floors, and each floor layout $$$F_i$$$ can be represented as an $$$R_i \times C_i$$$ 2D grid, where $$$R_i$$$ and $$$C_i$$$ are the dimensions of the $$$i$$$th floor. Also, each floor has a wall at its borders (to stop people from falling off and killing themselves). Each cell in the grid represents a 1x1 square meter of area, and is either an empty space, a wall, or a staircase. At each cell you can do the following:

• Cut a wall cell in the same floor into a door cell
• Walk to a nondiagonally adjacent cell in the same floor (either a door, a staircase, or plain empty space)
• If you are in a staircase, you can also travel to another floor connected by that staircase
• Cut a hole in the wall and fall to your death (not really recommended though)

You can do all of those moves instantly. However, with your laser running low and a villain to contain, you need to find a way to the top floor soon; in three seconds, to be exact. Since you were lucky enough to be on the ground floor when the Absconder initiated the lockdown, you want to start climbing the building in the optimal spot. It doesn't matter where in the top floor you arrive in, as long as you get there quickly enough. With knowledge of the layout of all floors, what is the minimum number of doors you need to cut down with your laser to get from the ground floor to the top floor?

First line contains an integer $$$f$$$, the number of floors in your headquarters. The floor plan $$$F$$$ follows. Each floor in the format is represented by the following format below: Each $$$i-th$$$ floor layout $$$F_i$$$ starts with a line containing two space-separated integers $$$R_i$$$ and $$$C_i$$$, the number of rows and columns of the 2D grid representing the floor. $$$R_i$$$ lines follow, each containing $$$C_i$$$ characters each, representing the floor layout itself:

• . - One unit of space within a room
• # - A wall
• an uppercase or lowercase letter (i.e., a-zA-Z) - a staircase

There are at most unique $$$52$$$ staircases (one for each uppercase/lowercase letter). If a staircase appears on another floor, it means that staircase connects those two floors together.

Constraints

$$$2 \le f \le 100$$$

$$$3 \le R_i,C_i \le 100$$$

No staircase is connected to a floor it is already in (staircases are unique per floor).

Output a single line with an integer $$$D$$$ indicating the total minimum number of walls you need to cut down into doors, counting all floors assuming you chose the optimal starting point in the ground floor.

If you cannot travel to the topmost floor (a path is impossible to make given the stairs), output the string "DAMN, THE ABSCONDER ABSCONDS AGAIN!" (without the quotes) instead.

3
8 8
########
#.A....#
#......#
########
#......#
#......#
#......#
########
8 8
########
#..#..B#
#..#...#
#..#####
#......#
#.######
#.#..A.#
########
8 8
########
#B#..#.#
#.#..#.#
########
#......#
#......#
#......#
########

2