В субботу была на Я 💛 фронтенд. Было много разных стендов с играми на любой вкус и цвет, мне пришлась по душе system design секция и сегодня я принесла вам с нее задачу. 📌 Дано: онлайн редактор таблиц (аля гугл таблицы). Пользователь может выделять ячейки как по одной, так и “оптом”, выделив сразу большой прямоугольник. А после этого он может удалить часть ячеек из выделенной зоны. В этом случае исходное выделение может разбиться на несколько поменьше, потому что любое выделение может быть строго прямоугольным — букву Г выделить не получится. Представим, что пользователь выделил квадрат 3х3 из ячеек, а затем убрал из выделения центральную ячейку. Выделение должно разбиться на 4: две горизонтальные полосы и еще два квадратика по бокам (см. рисунок). Как это вычислить на фронтенде? ✔️ Мое решение в лоб: ➖Поскольку нам нужно вычислять связанные ячейки, то необходимо пройтись по соседям в области исходного выделения => используем dfs ➖Т.к. нам нужно маркировать только прямоугольные области, модифицируем алгоритм таким образом, чтобы двигаться всегда вправо => таким образом, получим все выделенные зоны. Мне засчитали секцию и дали мерч, однако это примитивное решение в лоб является далеко не самым оптимальным. Предлагаю вам немного подумать и написать ваши варианты в комментарии, ну а затем я напишу решение, которое нравится мне 😏