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 or diagonal↵
↵
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—represent 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—reprsents 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.
↵
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 or diagonal↵
↵
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
↵
- N lines following, represent the map of the dungeon.↵
↵
Output format:↵
↵
- A single integer
↵
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.
