Russian Qt Forum

Квадратный участок размером NxN метров (N<200) разбит на клетки со стороной 1 метр. Клетка считается занятой, если на ней растёт дерево. Деревья рубить нельзя. Найти для строительствадома прямоугольник максимальной площади, свободный от деревьев. Минимальная сторона прямоугольника k вводится пользователем с клавиатуры. Визуализация и пошаговая демонстрация...

К сожалению, не знаю с чего начать и Qt только начинаю...это задание возможно сделать через массив кнопок или таблицей?при этом каждой ячейке или кнопке добавить значение 1 или 0 и относительно него цвет её? или совсем не так?

Для отображения использовать QTableView, а данные хранить в своей модели, отнаследованной от QAbstractItemModel.

А с чего нужно начать?

С решения на коленке :) А потом уже можно будет и визуальную часть прикрутить.

я просто хочу сначала сделать это поле заполненное двумя значениями и ячейками двухцветов а потом подумать над алгоритмом....а вот с чего начать не знаю

Если ты хочешь изучить Qt, начни с чтения книг. Если тебе нужно выполнить лабораторную, проще заплатить тому, кто ее за тебя сделает.

Это курсовая и я бы хотела в ней разобраться пока есть время...

Я бы конечно сначала начал с алгоритма решения, но раз хочешь наоборот, читай про модели и представления в книги Бланшета например.

На мой взгляд придумывать алгоритм куда интереснее чем копаться в подробностях чужих (пусть хороших) классов. Здесь видно так

1) Берем клетку на которой нет дерева и которая не помечена флажком Checked

2) Пытаемся "захватить" площадь, вправо и вниз. Проходит ли квадрат 2х2? А 3х3? Когда по одному направлению уткнулись в дерево, продолжаем попытки расшириться только по другому

3) Когда больше не удается "расшириться", запоминаем результат и маркируем все вошедшие клетки флагом  Checked. Возвращаемся к пункту 1 до тех пор пока не проверим все клетки

С чего начать: ну хоть с какой-то структуры данных для клетки. Отладить алгоритм печатая матрицу NxN в консоли, а потом уже рисовать UI (там ума много не надо)

Предложенный Igors алгоритм прост и удобен :)

А данные можно спокойно в модели хранить.

Вот только по пунку 1 - вместо флажка использовать data(32) со своим енумом(1 - занято, 0 - свободна от построек) :)

Если помечать все клетки очередного тестируемого прямоугольника, то возможна ситуация, когда мы клетку пометим при проходе небольшого прямоугольника и она будет не доступна, когда мы будет тестировать по настоящему максимальный прямоугольник.

Когда мы "расширяем" прямоугольник - флажок Checked игнорируется (учитывается только дерево). Только когда начинаем новый прямоугольник - флажок учитывается.

А вот с направлениями я наврал: надо расширяться не только "вправо и вниз" но еще и "вверх" - имеется ввиду проход строка за строкой

А есть и лучший способ (во всяком случае который найдет решение быстрее): найти все "левые верхние" и все "правые нижние" углы, и потом их сопоставить - сразу получаются прямоугольники

Если нет требований к скорости и задача учебная, то проще сделать за O(n⁴).
Перебор левых верхних вершин, перебор правых нижних и поиск максимального.

не могли бы вы побольше рассказать про этот алгоритм?

Найти все левые верхние углы. Каждое дерево может быть "ограничителем" прямоугольника. Это легко отловить 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 дерево по горизонтали и вертикали соответственно.

Данные: я бы держал деревья напр так
Чтобы удобно находить деревья в заданной строке/столбце (lower_bound)