Woburn Challenge 1999

Scarborough College (aka. the Concrete Palace) was affectionately known to its residents as The Rock. This contest affords a unique opportunity to determine why. While you all are stuck in a small cramped cell, (uh… room) with no food or drink, your proctors/captors will be enjoying themselves in a lavish staff room with coffee and donuts (mmm… Polish donuts). Some preliminary reconnaissance has revealed that they have some sensitive information vital to your sanity - the solutions to the contest. Apparently Tom Cruise failed to procure the solutions (see Problem 4) because he used so much hair gel that it underwent spontaneous combustion and set off the thermal sensors in the air vent. So some ambitious students decide to procure these documents themselves, but all of a sudden, the doors slam shut and the lights go out. Then a voice bursts out of the P.A. system speaker. "Do not be alarmed. I am The Plachta, the most feared teacher in the world (well, at least at Woburn)! I have wised up to your plan to steal the donuts and have taken corrective action by trapping you in your cell… uh, room. Do not try to escape because there are state-of-the-art surveillance cameras. The Plachta is watching you. Ha ha ha ha ha…"

Filled with fear, you do not know what to do. Before the competition started, however, you noticed that all the doors in the school were left unlocked (The Plachta sometimes overlooks these minor details). The doors are not a problem. All you have to do is avoid the security cameras and you will be free. Fortunately, one of the students on the UofT ACM team hacked into the city and stole the blueprints of the college and knows the positions of the cameras. All you need now is to figure out the shortest path that crosses the minimum number of cameras that will lead to an/any exit. Your task is to write a program that will find this path before it is too late…

Since Scarborough Campus consists of several buildings, there may be several maps in the input.

NOTE: The path must be the shortest one that crosses the minimum number of cameras (i.e. if the minimum number of cameras that you must cross to reach an exit is ~2~ and if there are several different paths which cross exactly ~2~ cameras, you must find the one with the shortest length). The starting square does NOT add to the length of the path.

The school map is a rectangular grid containing cells of the following type:

1 - Wall - You may not walk in these cells.

0 - Floor - You may walk in these cells.

C - Camera - This cell is a floor cell containing a camera. You may walk in these cells.

E - Exit - This is an exit.

S - Starting Position - This is where you start off.

• Woburn cameras actually are not as state-of-the-art as The Plachta thinks and have very short range. Crossing a camera occurs only when you step into a cell containing a camera.
• There will be at least one exit and at least one path that will lead from the starting position to an exit.
• There will be only one starting position.
• Not all exits or parts of the maze may be accessible.
• You may only move to adjacent cells (no diagonal moves) of all types except for type Wall.

Input Specification

The first line will contain ~m~ and ~n~, the width and height of the map ~(m \le 50, n \le 50)~
The next ~n~ lines will contain ~m~ digits ~(M_{x,y})~ each with no spaces (0=Floor, 1=Wall, C=Camera, E=Exit, S=Starting Position). This is the map.

$$\displaystyle \begin{matrix} M_{1,1} & M_{2,1} & \ldots & M_{m,1} \\ M_{1,2} & M_{2,2} & \ldots & M_{m,2} \\ \vdots & \vdots & \ddots & \vdots \\ M_{1,n} & M_{2,n} & \ldots & M_{m,n} \end{matrix}$$

Output Specification

Output ~N~ and ~L~ separated by a space. (~N~ = Number of cameras crossed in the path, ~L~ = length of the path) Input will be terminated by -1 -1.

Sample Input

50 20
11111111111111111111111111111111111111111111111111
111111100000000000C0000000000000000000001111111111
11111110111111111111111111111111111111100000000011
11111110111111111111111111111111111111111111111011
1S0000000000000000C0000000000000C11111111111111011
11101110111111111111111111111111011111111111111011
111C1110111111111111111111111111011111111111111011
11101110111111111100000000000000000000000000000E11
111C1110111111111101111111111111011111111111111111
11101110111111111101111111111111011111111111111111
111E11100000C0000000000000011111C1111000C000111111
11101111111101111111111111011111011111111110111111
11101111111101111111111111011111011111111110111111
11101111111101111111111111011111011111111110111111
11101111111100000000000000000000011111100C00111111
11101111111111111101111111011111011111101111111111
111000000000C0000001111111011111011111101111111111
11101111111111111111111111011111011111100011111111
111C00000000000000C0000000E00000E11111111000E11111
11111111111111111111111111111111111111111111111111
-1 -1

Sample Output

1 39

(NOTE: There are actually ~2~ paths of the same length that are correct)