Question

the city authorities need to know the number of houses in a residential area for future planning. the area is depicted in an aerial view and divided into an n x m grid. if a particular grid cell contains some part of the house roof, then it is given a value 1. if the cell is vacant, then it is given a value 0. clusters of adjacent grid cells with value 1 represent a single house. diagonal grids with value 1 do not represent the same house. write an algorithm to find the total number of houses in the area.

Answer 1

This algorithm uses a depth-first search to traverse through the grid, marking visited cells to avoid double-counting. It counts the number of houses based on the clusters of connected cells with the value 1.

def count_houses(grid):

def dfs(i, j):

if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == 0:

return

grid[i][j] = 0 # Mark the cell as visited

for x, y in directions:

dfs(i + x, j + y)

if not grid or not grid[0]:

return 0

rows, cols = len(grid), len(grid[0])

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

house_count = 0

for i in range(rows):

for j in range(cols):

if grid[i][j] == 1:

house_count += 1

dfs(i, j)

return house_count

# Example Usage:

grid = [

[1, 0, 1, 0, 0],

[1, 1, 1, 0, 1],

[0, 0, 0, 1, 0],

[1, 1, 1, 0, 0],

]

result = count_houses(grid)

print(f'Total number of houses: {result}')