Score : 700 points
Takahashi is locked within a building.
This building consists of H×W rooms, arranged in H rows and W columns.
We will denote the room at the i-th row and j-th column as (i,j). The state of this room is represented by a character A_{i,j}. If A_{i,j}= #
, the room is locked and cannot be entered; if A_{i,j}= .
, the room is not locked and can be freely entered.
Takahashi is currently at the room where A_{i,j}= S
, which can also be freely entered.
Each room in the 1-st row, 1-st column, H-th row or W-th column, has an exit. Each of the other rooms (i,j) is connected to four rooms: (i-1,j), (i+1,j), (i,j-1) and (i,j+1).
Takahashi will use his magic to get out of the building. In one cast, he can do the following:
His objective is to reach a room with an exit. Find the minimum necessary number of casts to do so.
It is guaranteed that Takahashi is initially at a room without an exit.
#
, .
or S
.S
, and it satisfies 2 ≤ i ≤ H-1 and 2 ≤ j ≤ W-1.Input is given from Standard Input in the following format:
H W K A_{1,1}A_{1,2}...A_{1,W} : A_{H,1}A_{H,2}...A_{H,W}
Print the minimum necessary number of casts.
3 3 3 #.# #S. ###
1
Takahashi can move to room (1,2) in one cast.
3 3 3 ### #S# ###
2
Takahashi cannot move in the first cast, but can unlock room (1,2). Then, he can move to room (1,2) in the next cast, achieving the objective in two casts.
7 7 2 ####### ####### ##...## ###S### ##.#.## ###.### #######
2