Let's imagine that the sides of the rectangle comprising the apartments are actually hallways.

Firstly, let's prove a statement that is going to help us in solving the task:

Statement: There is a hallway parallel to a side of the building that passes from one edge of the building all the way to the opposite edge.

Proof: Let's assume the contrary, that such a hallway does not exist.

Imagine that we are located at the start of a hallway (so, at the edge of the building) and start moving in the opposite direction. We move using the following algorithm: go straight until you hit an edge of an apartment. At that moment, when we can't continue straight anymore, look to the left and right. In one of these directions, we will not hit the building's edge for sure, because that would be contrary to the assumption that there is a hallway from one edge of the building to the other. Start moving in that precise direction.

Notice that we will enter a cycle at one point – from that moment on, we will be walking over the same part of the building. But that would mean that there is an apartment in the interior of that part of the building and that is impossible because that apartment wouldn't have a window. Therefore, the initial assumption is wrong and the statement is true.

We then proceed to solve the task using dynamic programming.

The current state can be described with dimensions of the building and 4 boolean values that tell us what part of the building we are located in (they represent the directions where the edge of the building is).

If all 4 boolean values are false, we return some large value because we cannot have an apartment in that part of the building.

On the contrary, we have 2 possibilities:

1. The whole of this part of the building is going to be an apartment.
2. We choose a hallway and split the building into two parts and recursively calculate the values of the dynamic for those parts of the building.