Baltic Olympiad in Informatics: 2014 Day 2, Problem 2

There is a cake placed in a labyrinth and you desperately want to eat it. You have a map of the labyrinth, which is a grid of ~R~ rows and ~C~ columns. Each grid cell contains one of the following characters:

• # which denotes a wall block,
• . which denotes an open square,
• S which denotes an open square of your current location,
• C which denotes an open square with the cake.

You may only walk on the open squares and move from one open square to another if they share a side. Additionally, the rectangular area depicted on the map is completely surrounded by wall blocks.

In order to reach the cake faster you have acquired a portal gun from Aperture Science™, which operates as follows. At any time it can fire a portal in one of the four directions up, left, down and right. When a portal is fired in some direction, it will fly in that direction until it reaches the first wall. When this happens, a portal will be spawned on the wall block, on the side that faces you.

At most two portals can exist at any given time. If two portals are already placed in the labyrinth, then one of them (selected by you) will be removed immediately upon using the portal gun again. Firing a portal at an existing portal will replace it (there may be at most one portal per side of wall block). Note that there may be two portals placed on different sides of the same wall block.

Once two portals are placed in the labyrinth you can use them to teleport yourself. When standing next to one of the portals, you can walk into it and end up at the open square next to the other portal. Doing this takes as much time as moving between two adjacent squares.

You may assume that firing portals does not take time and moving between two adjacent squares or teleporting through portals takes one unit of time.

Given the map of the labyrinth together with your starting location and the location of the cake, calculate the minimum possible time needed for you to reach the cake.

Constraints

Subtask 1 [11/100]

~1 \le R, C \le 10~

Subtask 2 [20/100]

~1 \le R, C \le 50~

Subtask 3 [20/100]

~1 \le R, C \le 200~

Every open square has at least one wall block adjacent to it.

Subtask 4 [19/100]

~1 \le R, C \le 200~

Subtask 5 [30/100]

~1 \le R, C \le 1\,000~

Input Specification

The first line of the input contains two space-separated integers: the number of rows in the map ~R~, and the number of columns ~C~. The next ~R~ lines describe the map. Each of these lines contains ~C~ characters: #, ., S or C (whose meaning is described above).

It is guaranteed that characters S and C each appear exactly once in the map.

Output Specification

The output should contain a single integer — the minimum time that is needed to reach the cake from the starting location.

You may assume that it is possible to reach the cake from your starting location.

Sample Input

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

Sample Output

4

Explanation for Sample

One quickest sequence of moves is as follows:

1. Move right.
2. Move right, shoot one portal up and one portal down.
3. Move through the bottom portal.
4. Move one square right and reach the cake.