Вырезание шахматных досок
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
- Матрицы и сетки
Дан прямоугольный лист из чёрных и белых клеток: список строк одинаковой длины из символов 0 и 1 (до 60 × 60). Шахматная доска — квадратный кусок листа со сторонами вдоль сторон листа, в котором любые две клетки с общей стороной разного цвета; квадрат 1 × 1 тоже доска.
Из листа по одной вырезают доски, пока клетки не кончатся. Каждый раз вырезают самую большую доску из оставшихся (целиком из ещё не вырезанных клеток); среди равных по размеру — ту, у которой верхняя строка выше, а при равенстве — ту, у которой левый столбец левее. Верните список пар [размер, количество]: сколько досок каждого размера вырежут, по убыванию размера, только размеры, которые встречаются.
Пример: ["0011", "0011", "1100", "1100"] → [[2, 1], [1, 12]].
Источник: Coding Competitions Archive, codejam/2010/round_1c/making_chess_boards · © Google LLC · Apache-2.0 · условие переведено и дополнено