Найти все левые верхние углы. Каждое дерево может быть "ограничителем" прямоугольника. Это легко отловить 2-мя проходами. Псевдокод прохода по строкам
C++ (Qt)
if (row < N - 1)
if (tree(row, col) && !tree(row + 1, col) {
int left = lookLeft(row + 1, col); // левое дерево в следующей (row + 1) строке (или -1)
int right = lookRight(row + 1, col); // правое дерево в следующей строке (или N)
for (int i = left + 1; i < right; ++i)
MarkHorz(row + 1, i);
}
По столбцам аналогично. Найденных углов будет не так уж много
Теперь для каждого угла P есть изначальный прямоугольник (P - точка (N, N)). Находим дерево внутри него которое образует с P минимальный прямоугольник (поиск по сортированным деревьям). Получаем 2 новых возможных прямоугольника, в которых находим ближайшее к P дерево по горизонтали и вертикали соответственно.
Данные: я бы держал деревья напр так
QVector <QVector <int> > mTreesHorz, mTreeVert;
Чтобы удобно находить деревья в заданной строке/столбце (lower_bound)
