# Can the dog reach the neighbour's house?

A dog is leashed to a pole and the owner wants to know if it can venture to the neighbour's building. You're given a map, which contains the pole (represented by x), the owner's buildings (represented by 1) and the neighbour's building (represented by 2). Empty areas are padded with dots and every line has the same length. EDIT: I forgot to mention, neighbour is always to the right from the dog. Every tile represents an area of one square meter. You're also given the length of the dog's leash (as meters). The pole is at the center of the tile. For input you must use the STDIN (and respectively STDOUT for output), if it's available in your language. Otherwise create a function, which takes the input as parameters and returns the answer. An example input to the STDIN would look like this.

6
............
...11..222..
...11..222..
...11.......
.x.11.......
............


Additional newline is guaranteed after the input. The program should output Yes if the dog can reach the neighbour's building and otherwise No.

## Assumptions

• There can be several buildings belonging to the owner.
• There can only be one neighbour's building.
• The dog can't venture outside the map or through the buildings.
• The dog can't be trapped inside a building.
• The length of the leash is always an integer
• Distances are calculated in Euclidean metric.

This is a codegolf, shortest code wins.

## Test cases

Input:

6
............
...11..222..
...11..222..
...11.......
.x.11.......
............


Output: No

Input:

7
............
...11..222..
...11..222..
...11.......
.x.11.......
............


Output: Yes

Input:

7
........
...11...
..111.22
..111.22
.x111.22
..111.22
..111...


Output: No

Input:

8
........
...11...
..111.22
..111.22
.x111.22
..111.22
..111...


Output: Yes

• What metric is used here? Manhattan? May 29, 2014 at 20:33
• @JanDvorak Euclidean metric May 29, 2014 at 20:38
• Could the downvoter explain? May 29, 2014 at 20:48
• Do you intend this to be a flood-fill solve? In other words, the dog can traverse only dots and if he can get from the x to any of the 2's in <= leash length dots then output yes, else no? May 29, 2014 at 21:02
• @DreamWarrior Reaching means even the slightest bit on top of. Also, the distance is not counted as dots but as Euclidean geometry's metres. This means the distance most often is a decimal number. May 29, 2014 at 21:04

## PHP 781 chars

I know this can be smaller but I am sorry that I am confused. If I take your first two examples (answers no and yes), if diagonal moves are not allowed, answers should be no and no, surely. If diagonal moves are allowed, answers should be yes and yes. Have I misunderstood?

I also took beside to be the criteria of 'reached' as the dog can then wee on the building - however changing that to on top of can easily be done changing the pass counter which currently equals leash length.

Anyway, this allows for diagonal movement, non diagonal would be smaller than this.

<?php
$a.='7 ............ ...11..222.. ...11..222.. ...11....... .x.11....... ...........';$b='No';$c=array();$d=array();function check_2($e,$f){if(($c[$e+1][$f-1]=='2')OR($c[$e+1][$f]=='2')OR($c[$e+1][$f+1]=='2')OR($c[$e][$f-1]=='2')OR($c[$e][$f]=='2')OR($c[$e][$f+1]=='2')OR($c[$e-1][$f-1]=='2')OR($c[$e-1][$f]=='2')OR($c[$e-1][$f+1]=='2')){return TRUE;;}else{return FALSE;}}str_replace("\n\r","\n",$a);$g=explode("\n",$a);$h=$g[0];unset($g[0]);$i=count($g);$j=0;foreach($g as$k){$l=str_split($k);$m=count($l)+1;unset($l[$m]);$c[$j]=$l;++$j;}$d=$c;for($n=0;$n<=$h;++$n){for($e=0;$e<$i;++$e){for($f=0;$f<$m;++$f){if($c[$e][$f]=='2'){$b='Yes';}if($c[$e][$f]=='x'){for($o=-1;$o<2;++$o){for($p=-1;$p<2;++$p){if($c[$e+$o][$f+$p]=='.'){$d[$e+$o][$f+$p]='x';}}}}}}$c=$d;}echo$b;?>


I am pretty sure I can make this smaller but with the confusion not sure which way to go.

Anyway this is my first flood fill so I am sure it can be done more efficiently. Most of the work was getting the input into a variable and a multi dimensional array.

The input it contained in the first variable \$a. You can see it here on codepad.

I hope you like it. As a relative newbie and since this is the only answer I suppose I am officially winning here at the moment. Although I cannot imagine this will last long if someone else enters :-)

• Sorry about the confusion and thanks for trying! The challenge itself is a bit flawed. Diagonal movement is totally allowed, but you should always strive for the shortest path. In the first example, shortest path from the first house to the second is diagonally. Also, I hope you're not counting the map in your score :) Jul 19, 2014 at 7:51
• Yes I was counting the map, although I asked on a chat room about it and they said it was ok not to. I suppose I could take 90 characters off but as I haven't tested it nor redone the codepad fiddle I will leave it for now. :-) PS I thought it had the makings of a great question. Jul 19, 2014 at 8:50
• I also elaborated the distannce calculation with this picture puu.sh/ahQ77/19d71e488e.png Jul 19, 2014 at 9:21
• I can see how to do it with one building. But with multiple owner buildings it seems I can always produce a map that makes my method incomplete. I am also assuming that the neighbour is always to the right of x, which is not correct either and again would make the program enourmous. (Also assuming the buildings are always rectangular, not L shapes or more complex, and not touching corners either. :-( Jul 19, 2014 at 11:53
• Wow, I completely forgot to mention that. Neighbours are always to the right. Jul 19, 2014 at 12:05