Portal Maze

You are given a maze with R rows and C columns. Each cell of the maze contains one character:

• #: a wall, which cannot be entered or passed.
• .: an open cell, which can be walked on.
• S: the starting point, which appears exactly once.
• C: the destination, which appears exactly once.

The maze is then expanded by adding an extra layer of walls (#) around its boundary. Thus the effective maze becomes of size (R+2)×(C+2).

Besides normal walking, you have a very special move: portal jump. At any moment you may shoot a portal in one of the four directions (up, left, down, right). The portal shot will travel in the chosen direction until it touches a wall; at that moment the portal will be attached to that wall. Note: You can use portal shooting arbitrarily many times without time cost.

A portal jump can be performed if you are standing in a cell that is immediately adjacent to a wall where a portal can be placed. More precisely, if you are in a free cell and in one of the four directions the immediate neighbor is a wall, then a portal shot from the opposite side of that same wall can be used to enter from that cell and exit on the other side of the wall – provided that the cell on the opposite side of the wall is a free cell. Using a portal jump costs 1 time unit.

You may also walk normally to an adjacent free cell in the up, down, left or right direction – which costs 1 time unit per move.

Your task is to compute the minimum time required to travel from the starting point S to the destination C in the expanded maze.

If you have any difficulty understanding the problem statement, please refer to the sample test cases.

inputFormat

The first line contains two integers R and C representing the number of rows and columns of the original maze.

Then follow R lines, each containing a string of length C composed of characters among {#, ., S, C}.

Note: The maze will then be automatically expanded by adding a border of walls (#) around it, making it of size (R+2)×(C+2).

outputFormat

Output a single integer – the minimum time required to go from cell S to cell C using normal moves and/or portal jumps.

sample

3 3
S..
.#.
..C

4