Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Recursive solution in Clear category for Calculate Islands by Amachua
def getArea(data, i, j):
# Check the rows and return 0 if outside the range
if i == len(data) or i < 0:
return 0
# Check the column and return 0 if outside the range
if j == len(data[0]) or j < 0:
return 0
if not data[i][j]:
return 0
# Set 0 at this position
data[i][j] = 0
# Recursively check all the connection
gs = 1 + getArea(data, i+1, j) + getArea(data, i, j+1) + getArea(data, i, j-1) + getArea(data, i-1, j)
gs += getArea(data, i+1, j+1) + getArea(data, i-1 ,j+1) + getArea(data, i+1, j-1) + getArea(data, i-1, j-1)
return gs
def checkio(data):
islands = []
for i in range(len(data)):
for j in range(len(data[0])):
# Check if it's an island
if not data[i][j]:
continue
# Get the area
area = getArea(data, i, j)
islands.append(area)
return sorted(islands)
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]]) == [1, 3], "1st example"
assert checkio([[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 0]]) == [5], "2nd example"
assert checkio([[0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0]]) == [2, 3, 3, 4], "3rd example"
June 28, 2013
Comments:
