Тут нужно уметь брать сумму на прямоугольнике. Дома = 1, пусто = 0. потом бежишь цикликом по всем возможным правым нижним ушлам твоего будущего дома и смотришь какая сумма на прямоугольнике, которую н покрывает. Если 0, то дом можно строить, иначе нельзя.

Осталось научиться брать сумму на прямоугольнике. Эта задачка подобна следующей задачке: находить сумму на отрезках массива. Тут нужно пользоваться частичными суммами.

Main idea is to check does __i, j position can be down right corner, which means that you have height __i with no trees and width __j with no trees. Whole dp point is saving how much trees you have above and how much trees you have left from current position. Obviously that can not guarantee if there is tree on diagonal, so you need to do aditional checks.

it's pretty easy — for each cell check whether it can be top left corner of AxB rect. or not. It can be done in linear time — firsly, count prefix sums A, such that S[i][j] = number of tress in rect. (1, 1) _ (i, j) (count this using some ez dp ideas) . Now u can count number of tress in any rect. using simple math. with S. So, for each cell(i, j) check whether there are no tress in rect (i, j) _ (i + a — 1, j + b — 1). Inglesh is dead, sorry for that