Maximal Square Visualizer

Интерактивный пошаговый симулятор алгоритма Maximal Square с оптимизацией памяти до O(cols).

Запуск

Понадобятся Node.js 20.19+ или 22.12+ и npm.

git clone https://github.com/FrankFMY/maximal-square-visualizer.git
cd maximal-square-visualizer
npm install
npm run dev

После запуска откройте http://localhost:5173. Для остановки сервера нажмите Ctrl+C.

В Windows также можно запустить START_APP.bat из папки клонированного проекта: скрипт установит зависимости при необходимости и откроет приложение в браузере.

Что можно делать

• запускать и ставить алгоритм на паузу;
• двигаться на один кадр назад и вперёд;
• переходить сразу в начало или финал;
• выбирать скорость 0.5×, 1×, 2×, 4×;
• использовать клавиши Space, ←, →, Home, End;
• кликать по ячейкам матрицы и менять 0 ↔ 1;
• видеть исполняемую строку TypeScript;
• следить за r, c, temp, prev, top, left, diagonal, dp[c], maxSide;
• видеть текущий квадрат и лучший найденный квадрат.

Главная идея алгоритма

После обработки ячейки [r][c] значение:

dp[c]

означает сторону самого большого квадрата из единиц, который заканчивается именно в [r][c].

Если текущая ячейка равна 1, размер квадрата определяется тремя соседями:

top       = старое dp[c]
left      = новое dp[c - 1]
diagonal  = prev

Формула:

dp[c] = Math.min(top, left, diagonal) + 1;

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

Зачем нужен temp

Перед вычислением мы сохраняем:

const temp = dp[c];

dp[c] сейчас содержит top, но скоро будет перезаписан новым значением. Сохранённый temp станет диагональю для следующего столбца:

prev = temp;

Почему память O(cols)

Полная DP-таблица не нужна. Для текущей строки достаточно:

• одной полоски dp шириной cols;
• одной переменной prev для диагонали.

Время остаётся O(rows × cols), память — O(cols). Это асимптотически оптимально по времени: в общем случае алгоритм обязан проверить каждую ячейку хотя бы один раз. Одномерная DP-полоска также исключает лишнюю таблицу rows × cols.

Сам визуализатор дополнительно хранит неизменяемые кадры выполнения для перемотки и пояснений. Эта память относится только к учебному trace-слою и не требуется базовому алгоритму.

Обработка пустого входа

Алгоритм сразу возвращает 0, если матрица пуста или не содержит столбцов:

if (!matrix.length || !matrix[0]?.length) {
  return 0;
}

В визуализаторе prev = 0 явно выполняется в начале каждой строки. Это делает инвариант диагонали очевидным и не зависит от специальной обработки первого столбца.

Проверки проекта

npm run lint
npm test
npm run check
npm run build

Проверяются:

• правильный ответ 9 для исходной матрицы;
• рост квадрата на [3][4] из top=2, left=2, diagonal=2;
• совпадение с независимым полным перебором для всех 682 бинарных матриц размеров до 3×3;
• отклонение ломаной матрицы;
• безопасный whitelist UI-действий и строгие границы координат;
• границы переходов проигрывателя;
• расчёт задержки для каждой скорости;
• TypeScript и production build.

Структура

src/
  example-matrix.ts  исходная матрица 6×7
  trace.ts           алгоритм и генератор неизменяемых кадров
  trace.test.ts      тесты алгоритма
  interaction.ts     безопасный dispatch и проверка координат
  interaction.test.ts тесты hostile UI-входов
  player.ts          переходы и скорость проигрывателя
  player.test.ts     тесты проигрывателя
  main.ts            интерфейс и взаимодействия
  styles.css         адаптивный визуальный слой

Автор

Artie Frank (@FrankFMY)

Лицензия

Проект распространяется по лицензии MIT.