A collection of implementations of common algorithms
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 59 lines 1.4 KiB Raw Permalink Blame History

 `#! /usr/bin/env python3` ``` ``` `# counts the number of regions in a matrix` `# vertically and horizontally connected` `# e.g.` `# [1, 0, 1, 1]` `# [0, 1, 0, 0]` `# [1, 1, 0, 1]` `# has 4 regions` ``` ``` `class Patch(object):` ` def __init__(self, visited, value):` ` self.visited = visited` ` self.value = value` ``` ``` ` def __repr__(self):` ` return "visited = %s, value = %s" % (self.visited, self.value)` ``` ``` `def initialize(region):` ` for row in region:` ` yield [Patch(visited=False, value=field) for field in row]` ``` ``` `testregion = list(initialize([` ` [True, False, True, True],` ` [False, True, False, False],` ` [True, True, False, True]` `]))` ``` ``` `def exploreField(region, x, y):` ``` ``` ` # check if we've reached the edge of the matrix` ` if (x < 0 or y < 0):` ` return True` ` try:` ` if region[y][x].visited or not region[y][x].value:` ` return True` ` except IndexError:` ` return True` ``` ``` ` region[y][x].visited = True` ``` ``` ` exploreField(region, y+1, x)` ` exploreField(region, y-1, x)` ` exploreField(region, y, x+1)` ` exploreField(region, y, x-1)` ``` ``` `count = 0` ``` ``` `for y, row in enumerate(testregion):` ` for x, patch in enumerate(row):` ``` ``` ` # if a patch is both unvisited and true` ` # this means exploreField will eliminate it` ` # so it counts as one region` ` if not patch.visited and patch.value:` ` count += 1` ` exploreField(testregion, x, y)` ``` ``` ```print(count) ``` ``` ```