{"raw_statement":[{"iden":"problem statement","content":"Takahashi is locked within a building.\nThis 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.\nEach 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)$.\nTakahashi will use his magic to get out of the building. In one cast, he can do the following:\n\n*   Move to an adjacent room at most $K$ times, possibly zero. Here, locked rooms cannot be entered.\n*   Then, select and unlock at most $K$ locked rooms, possibly zero. Those rooms will remain unlocked from then on.\n\nHis objective is to reach a room with an exit. Find the minimum necessary number of casts to do so.\nIt is guaranteed that Takahashi is initially at a room without an exit."},{"iden":"constraints","content":"*   $3 ≤ H ≤ 800$\n*   $3 ≤ W ≤ 800$\n*   $1 ≤ K ≤ H×W$\n*   Each $A_{i,j}$ is `#` , `.` or `S`.\n*   There uniquely exists $(i,j)$ such that $A_{i,j}=$ `S`, and it satisfies $2 ≤ i ≤ H-1$ and $2 ≤ j ≤ W-1$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$ $K$\n$A_{1,1}A_{1,2}$...$A_{1,W}$\n:\n$A_{H,1}A_{H,2}$...$A_{H,W}$"},{"iden":"sample input 1","content":"3 3 3\n#.#\n#S.\n###"},{"iden":"sample output 1","content":"1\n\nTakahashi can move to room $(1,2)$ in one cast."},{"iden":"sample input 2","content":"3 3 3\n###\n#S#\n###"},{"iden":"sample output 2","content":"2\n\nTakahashi 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."},{"iden":"sample input 3","content":"7 7 2\n#######\n#######\n##...##\n###S###\n##.#.##\n###.###\n#######"},{"iden":"sample output 3","content":"2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}