Description
episode 1: http://140.114.86.238/problem/12254/
episode 2: http://140.114.86.238/problem/12436/
episode 3: http://140.114.86.238/problem/12522/
After Iron Man grab all the infinity stones from Thanos and set them onto his hand, he now has the ability to decide the destiny of the whole universe...
After snapping, Iron Man's mind is teleported into the deepest layer of the stones. He knows who he have to eliminate, that is, the Thanos army.
Iron Man & Thanos thinking about this problem.
If you click Iron Man, something might happen...
Iron Man's mind is now located in a 2-dimension flat with lives of all creatures. He can eliminate any creature by stepping on it. Most lives are innocent creatures, and Iron Man doesn't want to eliminate them. Those lives he wants to eliminate is only the Thanos army.
As he is now in a spiritual form, he can split himself, search, and eliminate Thanos army in every direction at the same time. He can only walk up, down, left, and right. Diagonal movement such as up-left or down-right is not allowed.
Iron Man wants to know the minimum distance he have to walk in order to eliminate all the Thanos army.
You are given a flat.
Every position may be in the following state:
.: There's nothing here, you can pass this place without worrying.I: Here is the initial position you're at. There will be exactly oneIon the flat.T: The Thanos army are represented as aT. You have to eliminate allTon the flat. To eliminate them, you have to step onto every place with stateTat least once.C: All other innocent creatures. You cannot pass by or walk on this place since Iron Man don't want to eliminate innocents.
You're going to find out the minimum furthest distance that you need to walk.
Take sample as an example, the distance is marked below, and those red places is the place where you have to go through.
323C9
C1C98
C0CC7
212C6
CC345
Input
The first line contains two integers and .
There are lines below. Each line contains characters, indicate the state of all positions of the flat initially.
.
Output
Output the minimum distance that Iron Man have to walk in order to eliminate all the Thanos army. If it's impossible, output -1.