# Counting squares in a grid that is subdivided by line segments

Problem:

Given a picture of square with a bunch of horizontal and vertical lines in it (lines are not necessarily spanning the full square length, in other words think of a fine grid with many holes in it), design data structure(s) representing the data and a function that returns a number of squares pictured.

My ideas for the solution (in Python 2.7) are:

1. Using a enum to represent if a cell in a square has left, right, top and bottom border, and initial square with 4 borders;
2. For each horizontal line, the cell above the line has bottom border, and the cell under the line top border;
3. For each vertical line, the right cell has left border and the left border has right border;
4. Count how many cells have 4 borders, the result is the # of sub-squares.

Any advice on better data structure/method design, better algorithm performance in terms of time complexity, or code style advice are highly appreciated.

class SquareBorder:
has_left = 1
has_right = 2
has_top = 4
has_bottom = 8

def init_square(matrix):
for col in range(len(matrix[0])):
matrix[0][col] |= SquareBorder.has_top
matrix[len(matrix)-1][col] |= SquareBorder.has_bottom
for row in range(len(matrix)):
matrix[row][0] |= SquareBorder.has_left
matrix[row][len(matrix[0])-1] |= SquareBorder.has_right

def add_horizonal_line(matrix, row, start_col, end_col): # on top of row
for col in range(start_col, end_col + 1):
matrix[row][col] |= SquareBorder.has_top
matrix[row-1][col] |= SquareBorder.has_bottom
def add_vertical_line(matrix, col, start_row, end_row): # on left of col
for row in range(start_row, end_row + 1):
matrix[row][col] |= SquareBorder.has_left
matrix[row][col-1] |= SquareBorder.has_right

def find_squares(matrix):
result = 0
has_four_borders = SquareBorder.has_right | SquareBorder.has_left | SquareBorder.has_bottom | SquareBorder.has_top
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == has_four_borders:
result += 1
return result

if __name__ == "__main__":
'''
_ _ _
|_|_ _|
|_|_ _|
|_|_|_|
'''
size = 3
matrix = [[0] * size for _ in range(size)]
init_square(matrix)