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 — the dungeon has the size N*M.↵
↵
—- 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↵
↵
****#****↵
↵
*..#.#..*↵
↵
****.****↵
↵
*$#.#.#$*↵
↵
*********↵
↵
↵
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:↵
↵
↵
↵
Output format:↵
↵
↵
Example input:↵
↵
5 9↵
↵
****#****↵
↵
*..#.#..*↵
↵
****.****↵
↵
*$#.#.#$*↵
↵
*********↵
↵
↵
Example output:↵
4↵
↵
↵
Thank you guys, hope you have a great standing in the next contest.
