{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.)\n\nFurthermore, 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. \n\nFortunately, 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: \n\nYou 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?\n\nFirst 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 -t h$ 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: \n\nThere 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.\n\n*Constraints*\n\n$2 <= f <= 100$\n\n$3 <= R_i, C_i <= 100$\n\nNo staircase is connected to a floor it is already in (staircases are unique per floor).\n\nOutput 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.\n\nIf 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.\n\n"},{"iden":"input","content":"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 -t h$ 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 <= f <= 100$$3 <= R_i, C_i <= 100$No staircase is connected to a floor it is already in (staircases are unique per floor)."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ f \\in \\mathbb{Z} $ be the number of floors, with $ 2 \\leq f \\leq 100 $.  \nFor each floor $ i \\in \\{1, \\dots, f\\} $:  \n- Let $ R_i, C_i \\in \\mathbb{Z} $ denote the dimensions of the $ i $-th floor grid, with $ 3 \\leq R_i, C_i \\leq 100 $.  \n- Let $ F_i \\in \\{ \\text{empty}, \\text{wall}, \\text{staircase} \\}^{R_i \\times C_i} $ be the grid representation of floor $ i $.  \n- Let $ S \\subset \\Sigma $ be the set of unique staircase identifiers, where $ \\Sigma $ is the set of 52 alphanumeric characters (A-Z, a-z).  \n- A staircase labeled $ s \\in S $ on floor $ i $ connects to the same label $ s $ on another floor $ j \\neq i $.  \n\n**Constraints**  \n1. Each floor has border walls (outer perimeter cells are walls).  \n2. Each staircase label appears on exactly two distinct floors.  \n3. Movement is allowed between adjacent (up/down/left/right) **empty** cells on the same floor without cutting.  \n4. Movement between two floors via a staircase requires no laser cut (free teleportation).  \n5. Movement through a **wall** cell requires cutting one door (cost = 1).  \n6. Start: any empty cell on floor 1 (ground floor).  \n7. Target: any empty cell on floor $ f $ (top floor).  \n8. Goal: minimize total number of wall cuts (doors) across all floors.  \n\n**Objective**  \nCompute the minimum number of wall cuts $ D $ required to reach floor $ f $ from floor 1 via valid paths (including staircase teleportations), or output \"_DAMN, THE ABSCONDER ABSCONDS AGAIN!_\" if no such path exists.  \n\nFormally:  \nLet $ G = (V, E) $ be a graph where:  \n- Each vertex $ v \\in V $ is a tuple $ (i, r, c) $, representing position $ (r,c) $ on floor $ i $.  \n- An edge exists between $ (i, r, c) $ and $ (i, r', c') $ if $ |r - r'| + |c - c'| = 1 $ and both cells are **not walls**; cost = 0 if both are empty, cost = 1 if one is a wall.  \n- An edge exists between $ (i, r, c) $ and $ (j, r', c') $ if $ F_i[r][c] = F_j[r'][c'] = s \\in S $ and $ i \\neq j $; cost = 0.  \n\nFind the shortest path (minimum cost) from any $ (1, r, c) $ with $ F_1[r][c] \\neq \\text{wall} $ to any $ (f, r, c) $ with $ F_f[r][c] \\neq \\text{wall} $.  \nLet $ D $ be this minimum cost. If no path exists, output the failure string.","simple_statement":"You are on the ground floor of a building with f floors. You must reach the top floor by moving through stairs and cutting through walls with a laser. Each floor is a grid of cells: walls, empty spaces, or stairs (marked by letters). You can move freely in empty spaces on the same floor (up/down/left/right), but to change floors, you must step on a staircase that connects to another floor. You start anywhere on the ground floor. You can end anywhere on the top floor. Each time you cut through a wall to create a door, it counts as 1. Find the minimum number of walls you must cut to reach the top floor. If impossible, output: \"_DAMN, THE ABSCONDER ABSCONDS AGAIN!_\"","has_page_source":false}