Во-первых, не очень понятно, зачем вам вообще это. Агрегируя квадратики в прямоугольники вы будете находить не самые короткие пути в этом графе. Каким алгоритмом вы дальше в графе работаете? Какой-нибудь
Jump point search на неаггрегированных клетках может быть быстрее чего-бы то нибыло по аггрегированным.
Далее, если вам так хочется, то ваша задача аггрегирования - NP и кроме полного перебора вы не найдете оптимальное решение. Но вам, похоже, подойдет какое-нибудь достаточно хорошее решение, а не только оптимальное. Тогда будут работать всякие жадности и эвристики. Можно, например, брать самую левую-верхнюю непокрытую клетку и жадно растить вокруг нее максимальный по площади прямоугольник, который не пересекает ни одну покрытую или запрещенную клетку (допустим, перебирая нижнюю и верхнюю границу и жадно раздувая левую и правую до максимума). На примере из вопроса этот алгоритм построит 7 прямоугольников.
