Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Just DFS solution in Speedy category for Calculate Islands by Renelvon
from itertools import product
def checkio(data):
"""
Perform a DFS from each land-square not yet searched.
The first time a land-square enters the DFS stack,
make it a sea-square (it cannot belong to more than one island).
Complexity: Each sea-square is visited once. Each land-square is
visited at most twice. O(1) ops per visit ==> O(rows * columns)
"""
rows, cols = len(data), len(data[0])
islands = []
for i in range(rows):
for j in range(cols):
if data[i][j]: # Unexplored island: begin DFS from data[i][j].
stack = [(i, j)]
data[i][j] = 0 # Square inserted to stack becomes explored.
count = 1 # total number of new land-squares found
while stack:
ii, jj = stack.pop()
check_rows = (max(ii - 1, 0), ii, min(ii + 1, rows - 1))
check_cols = (max(jj - 1, 0), jj, min(jj + 1, cols - 1))
for iii, jjj in product(check_rows, check_cols):
# Set square to explored. Retain previous value.
prev, data[iii][jjj] = data[iii][jjj], 0
if prev: # If square was previously unexplored...
stack.append((iii, jjj))
count += 1
islands.append(count) # Done exploring this island!
islands.sort()
return islands
#These "asserts" using only for self-checking and not necessary for auto-testing
May 24, 2014
