Description

a180285 was luckily chosen as an exchange student from Earth to the Meow Planet—actually as an agent to investigate whether the Meowians intend to invade Earth. The Meowians do plan to invade Earth! After obtaining the exact information from a180285, the Earth task force decided to devise an anti-invasion plan.

A mandatory route from the Meow Planet to Earth can be viewed as an $n\times m$ grid. The Meowians will start from position $S$ on the map, and their destination is Earth’s entrance $T$. To resist the Meowian invasion, the Earth Defense Team plans to place some turrets on grid cells (at most $K$ turrets). A turret attacks in all $8$ directions (the $8$ directions are: east, south, west, north, northeast, northwest, southeast, southwest) (as shown in the figure below, a turret in the center cell can attack the eight surrounding cells). In addition, the Earth Defense Team can place an unlimited number of obstacles on the map so that the Meowians cannot pass through cells with obstacles.

The figure shows an example on a $3\times 3$ map, where $\tt X$ denotes a turret and $\tt \#$ denotes an obstacle. Cells containing a turret or an obstacle are impassable to the Meowians. On this map, the damage taken by the Meowians when moving from $S$ to $T$ is as follows:

• At $S(1, 0)$, the damage is $2$ (the turrets at $(0,0)$ and $(2, 1)$ can attack $S$).
• At the empty cell $(1,1)$, the damage is $3$ (simultaneously attacked by the turrets $(0,0)$, $(0,2)$, and $(2, 1)$).
• At $T(1,2)$, the damage is $2$ (the turrets at $(0,2)$ and $(2, 1)$ can attack $T$).

Therefore, the total damage is $2+3+2=7$.

As a member of the Earth Defense Team, please arrange the placement so that the Meowians take the maximum possible damage. Note that if there are multiple paths from $S$ to $T$, the Meowians will choose the one with the minimal damage.

Input Format

The first line contains three integers $n,m,K$, denoting the number of rows and columns of the map, and the maximum number of turrets that can be placed.

The next $n$ lines each contain $m$ characters: $\tt \#$ denotes an existing obstacle on the map, $\tt .$ denotes an empty cell, $\tt S$ denotes the start, and $\tt T$ denotes the destination. It is guaranteed that in the original map there exists a path from $S$ to $T$.

Output Format

Output the maximum damage the Meowians will take under an optimal placement, assuming they take the optimal route.

Note that after the placement, you must still ensure that the Meowians can reach the destination $T$ from the start $S$ along at least one path; otherwise, they will organize an even larger-scale invasion.

3 3 1
S.T
...
...

7

Hint

Sample Explanation

One optimal layout for the sample is as follows:

S#T
.X.
...

Constraints

• For $30\%$ of the testdata, $1\le n,m\leq 6$.
• For $100\%$ of the testdata, $\min(n,m)\le 6$, $\max(n,m)\le 20$, $1\le K\le 15$, and a path from $S$ to $T$ always exists.

Translated by ChatGPT 5