{"problem":{"name":"Closed Rooms","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc014_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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$.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc014_c","tags":[],"sample_group":[["3 3 3\n#.#\n#S.\n###","1\n\nTakahashi can move to room $(1,2)$ in one cast."],["3 3 3\n###\n#S#\n###","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."],["7 7 2\n#######\n#######\n##...##\n###S###\n##.#.##\n###.###\n#######","2"]],"created_at":"2026-03-03 11:01:14"}}