Описание задачи
Дана матрица чисел. Найти самый большой квадратный участок, где каждая клетка ≥ min.
Алгоритм
- Получаем пороговое значение
min - Строим бинарную карту: 1 если cell ≥ min, 0 иначе
- Ищем самый большой квадрат из единиц (классическая DP-задача)
Формат входных данных
> Map:
cols rows
v11 v12 v13 v14
v21 v22 v23 v24
...
> Query:
min_threshold
Формат выходных данных
Largest: NxN
* (x1, y1)
* (x2, y2)
...
Если ни одна клетка не удовлетворяет порогу — Does not exist.
Пример
Карта 4×4
> Map:
4 4
3 8 2 2
1 4 5 6
7 1 2 3
0 9 1 6
Query: 2
Largest: 2x2
* (1,0)
* (2,0)
* (2,1)
Клетки ≥ 2 образуют несколько квадратов 2×2. Выводятся левые верхние углы.
Query: 10
Does not exist.
Ключевые моменты
- DP-формула: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- dp[i][j] = 0 если клетка < min
- Максимум в таблице DP = размер наибольшего квадрата