Given a map of a dungeon, your task is to take all TWO diamonds in the dungeon.
Find the minimum number of gates you have to open to take all the diamonds.
Note: It can be more than one gate to go into the dungeon from the outside.
You can move up, down, left, right.
About the map:
The letter '.' means blank space, you can move on it
The letter '*' means blockade, you have to go around it
The letter '#' means there's a gate at that place, you need it opened to go through it
The letter '$' means the diamond.
Input format:
First line is two number N and M — the dungeon has the size N*M. (2 ≤ N,M ≤ 100)
N lines following, represent the map of the dungeon.
Output format:
- A single integer — the minimum number of gates you have to open.
Example input:
5 9
****#****
..#.#..
****.****
$$$#.#.#$$$
Sorry for the input, you can see read the input here : https://ideone.com/EXk0Wh
Example output:
4
Thank you guys, hope you have a great standing in the next contest.
