CSES - Walls and floors

A grid has n \times n squares, which are all walls initially. The rows and columns are numbered 1 \dots n. The walls are then gradually removed by converting them into floors.

Your task is to keep track of the number of rooms during the process. A room consists of a vertically or horizontally connected floor squares, as in earlier tasks on the course.

In a file wallgrid.py, implement the class WallGrid with the following methods:

  • create_floor converts he square (x,y) into a floor if it is not already a floor
  • count_rooms returns the number of rooms

Both methods should efficient even for a large grid.

class WallGrid:
    def __init__(self, n):
        # TODO

    def create_floor(self, x, y):
        # TODO

    def count_rooms(self):
        # TODO

if __name__ == "__main__":
    wall_grid = WallGrid(5)

    print(wall_grid.count_rooms()) # 0

    wall_grid.create_floor(2, 2)
    wall_grid.create_floor(4, 2)
    print(wall_grid.count_rooms()) # 2

    wall_grid.create_floor(3, 2)
    print(wall_grid.count_rooms()) # 1

    wall_grid.create_floor(2, 4)
    wall_grid.create_floor(2, 4)
    wall_grid.create_floor(4, 4)
    print(wall_grid.count_rooms()) # 3

    wall_grid.create_floor(3, 3)
    print(wall_grid.count_rooms()) # 3

    wall_grid.create_floor(3, 4)
    print(wall_grid.count_rooms()) # 1