Description

Given an $R \times C$ maze, each cell contains one type of tile:

• # Wall: you cannot walk onto it and cannot pass through it.
• . Floor: you can walk on it.
• S Start: the player starts here; there is exactly one.
• C Goal: the player must reach here; there is exactly one.

Now the maze is expanded by adding a layer of # tiles around it, becoming a $(R+2) \times (C+2)$ maze.

Also, at any time, the player can shoot a portal in one of the four directions: up, left, down, right. When a portal is shot, it keeps flying in the shooting direction until it touches a wall. At that moment, the portal is placed on that wall.

Moving one cell takes $1$ unit of time, and traveling through a portal also takes $1$ unit of time.

Find the minimum time needed to reach the goal from the start.

If the statement is hard to understand, please refer to the samples.

Input Format

The first line contains two integers $R, C$, representing the maze size.
The next $R$ lines each contain $C$ characters, describing the maze.

Output Format

Output one integer: the minimum time to reach the goal.

4 4
.#.C
.#.#
....
S...

4

Hint

Sample Explanation

For Sample $1$, after we simulate the maze and add # around it, it looks like the following figure:

The humanoid object is S, and the cake-shaped object is C.

As shown, at least $4$ units of time are needed.

Constraints

This problem uses bundled testdata.

• Subtask 1 (11 pts): $R, C \le 10$.
• Subtask 2 (20 pts): $R, C \le 50$.
• Subtask 3 (20 pts): $R, C \le 200$, and every . has at least one # adjacent to it.
• Subtask 4 (19 pts): $R, C \le 200$.
• Subtask 5 (30 pts): no special constraints.

For $100\%$ of the testdata, $1 \le R, C \le 1000$.

This problem forces $O2$ optimization.

Notes

Translated from BalticOI 2014 Day2 B Portals。

Translated by ChatGPT 5