# Determine if land is fully enclosed by fences

Imagine a two-dimensional array of boolean values, where the 0s represent squares of grass on a rectangular plot of land and the 1s represent fences.

Write a function that accepts the 2D array as an input and determines whether you can travel from any one area of grass to any other area of grass, using only north/east/west/south movements, without running into a fence.

If any area of grass in the array is fully enclosed by fences (meaning you can't travel N/E/W/S to reach every other area of grass in the array) the function should return false; otherwise, it should return true.

Below are two sample arrays you can use as inputs, although your function should be able to handle not just these but any 2D array of boolean values:

0 0 0 0 0
0 1 0 0 0
0 1 1 1 1
0 0 0 0 0
0 0 0 1 1

(should return true)

0 1 0 1 0
0 1 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 1 1 0

(should return false, since the middle 0 in the top row is fully enclosed)


Shortest working code wins. I'll pick the winner after either a week has passed or there have been no new submissions within 24 hours.

• Can you also forbid binary operators? I'd love to see what people would come up with. – Pierre Arlaud Jan 2 '14 at 14:28
• I do believe this is very similar to a USACO problem from last year (2012/2013 season). There are some huge test cases that can be accessed there... – apnorton Jan 2 '14 at 14:52
• Will the size of the array always be 5*5? – ProgramFOX Jan 2 '14 at 15:02
• @ProgramFOX Assume array could be any height, any width. And sure, output anything boolean. – jawns317 Jan 2 '14 at 16:02
• what about the 3X3 matrix 1 1 1; 1 0 1; 1 1 1? There is one grass cell in the center. Visually the grass cell in the center is fully enclosed by fences, but by your definition it is not. – emory Jan 3 '14 at 14:37

# Matlab 45

input('');c=bwconncomp(~ans,4);c.NumObjects<2

• @jawns317 I don't see why this is the accepted answer. This isn't a function. The only other answer that isn't a function accepts from stdin. This one doesn't even do that. – Tim Seguine Jan 17 '14 at 11:12
• Accepting standard input could be done as such input('');c=bwconncomp(~ans,4);c.NumObjects<2 This would make it 45 characters. – Dennis Jaheruddin Jan 29 '14 at 10:49

## APL (39)

{∧/,⊃{⍺∨⊖⍵}/{⍵∨(∧\~⍵)∨⌽∧\⌽~⍵}¨s,⊖¨s←⊂⍵}


Usage:

      board1 board2
0 0 0 0 0  0 1 0 1 0
0 1 0 0 0  0 1 1 0 0
0 1 1 1 1  0 0 0 0 0
0 0 0 0 0  0 0 0 1 0
0 0 0 1 1  1 1 1 1 0
{∧/,⊃{⍺∨⊖⍵}/{⍵∨(∧\~⍵)∨⌽∧\⌽~⍵}¨s,⊖¨s←⊂⍵} ¨ board1 board2
1 0

• The benefit of APL is that it looks so much like line noise that nobody wants to verify it is correct. – Tim Seguine Jan 2 '14 at 15:36
• @Tim Anyone can download an interpreter to run it and check. – Gareth Jan 2 '14 at 19:24
• @Gareth Yeah, The comment was supposed to be tongue in cheek. – Tim Seguine Jan 2 '14 at 20:33
• @Tim Oh sorry. Missed that. :-( – Gareth Jan 2 '14 at 23:00

# Mathematica, 60 58 chars

f=Max@MorphologicalComponents[1-#,CornerNeighbors->1>2]<2&


Usage:

f[{{0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 1}}]


True

f[{{0, 1, 0, 1, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 0}}]


False

• Same length f=Max@WatershedComponents[Image@#,CornerNeighbors->1>2]<2& – Dr. belisarius Jan 2 '14 at 18:25

# Ruby, 202198 193

a=$<.read.split(' ').map(&:split) f=->x,y{a[x][y]=1 [[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o,y+o f[d,e]if a[d]&&a[d][e]==?0}} f[i=a.index{|x|x.index ?0},a[i].index(?0)] p !(a.join=~/0/)  Does a flood-fill, then checks to see if there are any 0s left. • Damn! If I hadn't tested my code first I would have been faster. ;) – Tim Seguine Jan 2 '14 at 15:15 • @Tim But then it would have been wrong! :P – Doorknob Jan 2 '14 at 15:21 ## PHP 147 202177165149 bytes EDIT I beat my gzip hack with a real php solution. A little long.... input as a text string, no spaces, rows delimited by newlines. It flood fills with cs and then checks to see if there are any zeros left. In the loop I use exp as a crude upper bound on the number of iterations required. I take advantage of the symmetry to handle the duplicate cases in less code function f($s){$r=strpos;$n=$r($s,'
');$s[$r($s,'0')]=c;for(;$i++<1<<$n;)$s=strrev(ereg_replace('0(.{'.$n.'})?c','c\1c',$s));return!1==$r($s,'0');}


Here is an ungolfed test case:

<?php
$s1="00000 01000 01111 00000 00011";$s2="01010
01100
00000
00010
11110";

function f($s){$n=strpos($s,"\n");$s[strpos($s,'0')]=c; for(;$i<strlen($s);++$i)
$s=strrev(ereg_replace( '0(.{'.$n.'})?c',
'c\1c'
,$s)); return!1===strpos($s,'0');
}

var_dump(f($s1)); var_dump(f($s2));


## Excel VBA, 305 215 Bytes

Yes, haha VBA, but the matrix nature of the problem suggets a practical solution in Excel might be interesting (Plus someone has already submitted an answer in my other languages!). Obviously VBA is not going to be the most succinct, but I think it's reasonable.

This flood fills from an arbitrary starting point then checks if any "grass" left

R is a worksheet range with 1's and 0's representing the fences and grass as defined in the problem. Bonus, the playing field doesn't have to be rectangular or even contiguous.

0 1 1 1 1
0   0 0 0 0
0 1 1 1 1


For example, would return False. The zeros on the right can't be reached from the zeros on the left. The irregular field doesn't break it.

Function F(R)
L R, R.Find(0)
F = Not IsNumeric(R.Find(0))
End Function

Sub L(R, S As Range)
If S Or IsEmpty(S) Then Exit Sub
S = 1
L R, S.Offset(1, 0)
L R, S.Offset(-1, 0)
L R, S.Offset(0, 1)
L R, S.Offset(0, -1)
End Sub


Some notes on the golfing.

I think some chars could be trimmed if the requirement was inverted in regards to 1 and 0, but not enough to make it worth inverting.

VBA insists on a bunch a whitespace (a = b vs a=b), which doesn't help the char count.

S needs to be explicitly declared as a range. If it's left a variant, it turns into a range value rather than a range.

Maybe a better way to branch the flood? I couldn't come up with a loop that saved any chars to send it N/E/S/W

Edit: rethougt the base case on the flood fill, managed to trim quite a bit off by checking if it's at a base case after recursion rather than preventing the recursion.

# Python (219 bytes)

Definitely not the shortest, but it's my first try here, so I'm proud of it:

def f(n):
m=[int(c) for c in n if c!='\n']
for i in range(len(m)):
if m[i]<1:m[i]=2;break
g(m,n.find('\n'),i);return not 0in m
def g(n,w,i):
for x in i-w,i-1,i+1,i+w:
if 0<=x<len(n):
if n[x]<1:n[x]=2;g(n,w,x)


It's input should be a String of 0s & 1s where rows are delimited by a newline (\n) character.

Example usage:

>>> f("00000\n01000\n01111\n00000\n00011")
True
>>> f("01010\n01100\n00000\n00010\n11110")
False

• you can combine the last two if statements into one with and, I think it saves some chars – Tim Seguine Jan 2 '14 at 21:07
• You can use tabulator as 8 spaces. – Konrad Borowski Jan 2 '14 at 21:22

## Python (196)

Standard flood filling.

g=raw_input()
m=g.find(' ')
g=g.replace(' ','')
V={}
def D(V,x):
if V.get(x,0)or g[x]=='1':return
V[x]=1;[D(V,x+i)for i in 1,-1,m,-m if 0<=x+i<len(g)]
D(V,g.find('0'))
print len(V)==g.count('0')


Takes the matrix through STDIN with each row separated by a single space. For example "01010 01100 00000 00010 11110".

# Mathematica 53

f=Max@(Symbol@@Names@"I*i*B*l")[Image[1-#],0,1>2]<2&


It calls the internal function ImageMorphologicalOperationsDumpimageBinaryLabel, which is similar to MorphologicalComponents.

f[{{0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 1}}]
f[{{0, 1, 0, 1, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 0}}]


True

False

# PHP (286 chars)

Way too long, I probably went the long long way.

function D($a){$x=count($a);$y=count($a);for($i=0;$i<$x;$i++)$a[$i][-1]=$a[$i][$y]=1;for($j=0;$j<$y;$j++)$a[-1][$j]=$a[$x][$j]=1;for($i=0;$i<$x;$i++){for($j=0;$j<$y;$j++){if($a[$i][$j]!=1){if($a[$i][$j-1]==1&&$a[$i][$j+1]==1&&$a[$i-1][$j]==1&&$a[$i+1][$j]==1)return 0;}}}return 1;}


Non-golfed:

function D($a) {$x=count($a);$y=count($a); for ($i=0;$i<$x;$i++)$a[$i][-1]=$a[$i][$y]=1;
for ($j=0;$j<$y;$j++)
$a[-1][$j]=$a[$x][$j]=1; for ($i=0;$i<$x;$i++) { for ($j=0;$j<$y;$j++) { if ($a[$i][$j] != 1)
{
if ($a[$i][$j-1] == 1 &&$a[$i][$j+1] == 1 && $a[$i-1][$j] == 1 &&$a[$i+1][$j] == 1)
return 0;
}
}
}
return 1;
}

• This isn't correct. It only checks to see if there are no single zeros which are surrounded by ones. There are more complicated ways to wall off zeroes. – Tim Seguine Jan 2 '14 at 15:32
• Of course you are right. I was looking for another way to solve this without floodfills, I guess my search continues! – Vereos Jan 2 '14 at 16:13
• It is just a graph reachability problem, and floodfill in this case is basically floyd-warshall without explicitly creating or representing the reachability graph. You could try to extract the graph and do the transitive closure yourself, but my guess is it will be longer. – Tim Seguine Jan 2 '14 at 20:55

# C#, 235 Bytes

int[][]D;int w,h,n;bool Q(int x,int y){var r=x>=0&&x<w&&y>=0&&y<h&&(D[x][y]++==0);if(r){Q(x-1,y);Q(x+1,y);Q(x,y+1);Q(x,y-1);}return r;}
bool P(int[][]B){D=B;w=D.Length;h=D.Length; for(int i=0;i<w*h;i++)if(Q(i%w,i/w))n++;return n==1;}


It tries to flood fill every cell in the board, it it makes only one flood fill returns true.

bool R( int x, int y)
{
var r = (x >= 0 && x < w && y >= 0 && y < h && D[x, y]++ == 0);
if (r)
{
R(x-1, y);
R(x+1, y);
R(x, y+1);
R(x, y-1);
}
return r;
}

public bool Do()
{
D = Board1;
w = D.GetLength(0);
h = D.GetLength(1);
for (int x = 0; x < w; x++) for (int y = 0; y< h; y++) if (R(x, y)) n++;
return n == 1;
}


# Python 2.X + 3.X: 335 chararcters

Golfed:

def f(n):
x,y=0,0
z=lambda x,y:y<len(n)and x<len(n)and n[x][y]!=1
while not z(x,y):
y+=1
if y==len(n):
y=0
x+=1
if x==len(n):
return False
t=set([(x,y)])
v=set()
while t:
(x,y)=t.pop()
v|=set([(x,y)])
if z(x+1,y):
t|=set([(x+1, y)])
if z(x,y+1):
t|=set([(x, y+1)])
return len(v)+sum(map(sum,n))==len(n)*len(n)


Ungolfed:

def f(n):
"""In the following filed, starting from a 0: is it possible to
get to every other 0?

>>> f([[0,0,0,0,0],\
[0,1,0,0,0],\
[0,1,1,1,1],\
[0,0,0,0,0],\
[0,0,0,1,1]])
True
>>> f([[0,1,0,1,0],\
[0,1,1,0,0],\
[0,0,0,0,0],\
[0,0,0,1,0],\
[1,1,1,1,0]])
False
>>> f([[1,1,1,1,1],\
[1,1,1,1,1],\
[1,1,1,1,1],\
[1,1,1,1,1],\
[1,1,1,1,1]])
False
>>> f([[1,1,1,1,1],\
[1,1,1,1,1],\
[1,1,1,1,1],\
[1,0,1,1,1],\
[1,1,1,1,1]])
True
>>> f([[1,1,1,1,1],\
[1,1,1,1,1],\
[0,1,1,1,1],\
[1,0,1,1,1],\
[1,1,0,1,1]])
False
>>> f([[1,1,1,1,1],\
[1,1,1,1,1],\
[1,1,1,1,1],\
[1,1,1,1,1],\
[1,1,1,1,0]])
True
"""
x, y = 0,0
isValid = lambda x,y: y<len(n) and x<len(n) and n[x][y] != 1
for i in range(len(n)*len(n)):
x = i%len(n)
y = i/len(n)
if isValid(x,y):
break

while not isValid(x,y):
y += 1
if y == len(n):
y = 0
x += 1
if x == len(n):
return False # Problem is not clearly defined here
toGo=set([(x,y)])
visited=set()
while toGo:
(x,y) = toGo.pop()
visited |= set([(x,y)])
if isValid(x+1,y):
toGo |= set([(x+1, y)])
if isValid(x,y+1):
toGo |= set([(x, y+1)])
return len(visited)+sum(map(sum,n)) == len(n)*len(n)

if __name__ == "__main__":
import doctest
doctest.testmod()
`
• Could you move the golfed version to to the top? Some people have a user script for this site which counts the characters in the first block of code. – Gareth Jan 11 '14 at 19:46
• @Gareth: Done.. – Martin Thoma Jan 11 '14 at 19:49