поле N x N заполненное двумя значениями

[Dia28]

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

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

[Пантер]

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

[Dia28]

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

[ecspertiza]

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

[Dia28]

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

[Пантер]

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

[Dia28]

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

[ecspertiza]

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

[Igors]

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

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

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

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

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

[Bepec]

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

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

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

[BRE]

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

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

[Igors]

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

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

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

[Igors]

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

[SimpleSunny]

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

[Dia28]

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

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