---languages_supported:- NAtitle: B1category: NAold_version: trueproblem_code: B1tags:- NAlayout: problem---### All submissions for this problem are available.**This problem was part of the [CodeChef April Challenge](http://www.codechef.com/APRIL09/). All user submissions for this contest problem are publicly available [here](http://www.codechef.com/APRIL09/status/B1/).**Spaghetti Monsters have stolen The Chef’s golden spoon! The Chef has a map, on which are marked: his location, the location of the golden spoon, and the locations of the spaghetti monsters. The map is in fact rectangular, consisting of square fields. Each field on the map, except for those adjacent to the boundary, is adjacent to 8 other fields -- fields which share a side or corner are assumed to be at a distance of 1 from each other, and it is possible to move between them directly. The Chef is a bit scared of spaghetti monsters and would prefer not to approach them too closely... Help him compute the minimum distance up to which he must approach some spaghetti monster, so as to find the golden spoon.### InputThe first line of input contains two numbers 1<=n,m<=1000, where n denotes the height of the map, and m its width.The map is given in the next n lines, each of which consists of m characters:The unique field represented by the character '@' is the location of The Chef.The unique field represented by the character '$' is the location of the golden spoon.A field represented by the character 'D' is the location of a spaghetti monsters.All the remaining fields are represented by the character '.' and denote empty positions./>/>/>/>/>### OutputThe output should contain exactly one number, equal to the minimum distance, at which The Chef must find himself from one of the spaghetti monsters in order to reach the golden spoon.### Example 1<pre><tt><b>Input:</b>7 5....$..........D...D..........@....<b>Output:</b>2</tt></pre>### Example 2<pre><tt><b>Input:</b>7 5....$..........DDDDD..........@....<b>Output:</b>0</tt></pre>