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:↵
— 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.
