시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 74 | 21 | 19 | 41.304% |
The protagonist of this task, Chell, must solve a new puzzle GLaDOS has come up with. Chell is in a room whose layout that can be represented as a matrix of dimensions N rows and M columns. Each field can be one of the following:
Chell is carrying a so-called portal gun, a gun with which you can create portals in the walls. In each move, she can do one of the following:
Chell wants to know the minimal amount of time it takes for her to solve the puzzle, i.e. to reach the field denoted as ‘F’.
Please note: The room will always have walls on the sides, and letters ‘C’ and ‘F’ will appear only once in the matrix.
The first line of input contains the positive integers N and M (4 ≤ N, M ≤ 500), the numbers from the task.
Each of the following N lines contains M characters that describe the layout of the room.
You must output the minimal amount of time it takes to solve the puzzle, or “nemoguce” (without quotation marks, Croatian for impossible) if it is not possible to solve it.
4 4 #### #.F# #C.# ####
2
6 8 ######## #.##..F# #C.##..# #..#...# #.....## ########
4
4 5 ##### #C#.# ###F# #####
nemoguce
Clarification of the second test case:
The puzzle can be solved in 8 moves, illustrated in the pictures below.
In the first move, we turn towards the left wall, shoot and create a portal that appears on the wall in the 3rd row and 1st column (coordinates (3,1)) from the right side.
In the second move, we create a portal from the upper side of the wall at coordinates (6,2).
In the third move, we step into the portal at coordinates (3,1) and exit at coordinates (5,2) - a non-obstructed field with the second portal.
In the fourth move, we turn right and create a portal from the left side of the wall at coordinates (5,7). Since there are already two portals, the one at field (3,1) disappears.
In the fifth move, we step into the portal at coordinates (6,2) and exit at coordinates (5,6) with the second portal.
In the sixth move, we create a new portal from the lower side of the wall at coordinates (1,6), making the portal at coordinates (6,2) disappear.
In the seventh move, we step into the portal at coordinates (5,7) and exit at coordinates (2,6).
Finally, in the eighth move, we move one place to the right to end the game.
The portal creation in moves 1, 2, 4 and 6 lasts zero amounts of time, whereas the rest of the move last one unit of time, so the total time needed to solve the puzzle is 4 units of time.