🟡 Middle — двумерные массивы#
Четыре авторские задачи на эффективный обход матриц, префиксные суммы и осознанное использование дополнительной памяти.
1. Запросы по складу#
В таблице R × C хранятся количества товаров в ячейках склада. Затем поступают запросы прямоугольных областей. Для каждого запроса найдите сумму в прямоугольнике с верхним левым углом (r1,c1) и нижним правым (r2,c2), координаты включены и начинаются с нуля.
Ввод: R C Q (1 ≤ R,C ≤ 2000, 1 ≤ Q ≤ 2·10^5), затем матрица неотрицательных значений не больше 10^6, затем Q запросов r1 c1 r2 c2 с корректными координатами.
Вывод: сумма для каждого запроса в отдельной строке.
Пример:
3 4 2
1 2 3 4
5 6 7 8
9 10 11 12
0 1 1 2
1 0 2 3
18
68
Требование: предварительная обработка O(R*C), каждый запрос O(1), дополнительная память O(R*C). Используйте двумерные префиксные суммы и 64-битный тип; не проходите заново по каждой области.
2. Поворот изображения на 90 градусов#
Дана прямоугольная матрица пикселей размера R × C. Поверните её по часовой стрелке на 90 градусов и выведите результат размера C × R.
Ввод: R C (1 ≤ R,C ≤ 2000), затем R*C целых чисел a[r][c] (|a[r][c]| ≤ 10^9).
Вывод: сначала размеры C R, затем повернутая матрица. Элемент исходной клетки (r,c) переходит в (c, R-1-r).
Пример:
2 3
1 2 3
4 5 6
3 2
4 1
5 2
6 3
Требование: O(R*C) времени. Разрешён один выходной буфер O(R*C), но не создавайте несколько промежуточных копий. Обоснуйте, почему простая транспозиция на месте для прямоугольной матрицы не подходит.
3. Суммы соседей с минимальной памятью#
Для каждой клетки числовой матрицы вычислите сумму её соседей по стороне: сверху, снизу, слева и справа. Сама клетка не считается соседом. Для клеток на границе учитывайте только существующих соседей.
Ввод: R C (1 ≤ R,C ≤ 2000), затем R*C целых чисел a[r][c] (|a[r][c]| ≤ 10^6).
Вывод: матрица сумм того же размера.
Пример:
2 3
1 2 3
4 5 6
6 9 7
7 10 8
Требование: O(R*C) времени и не более O(C) дополнительной памяти сверх входной матрицы. Сначала считайте исходные данные, затем обрабатывайте построчно, сохраняя только строки, необходимые для вычисления. Выводите результат сразу, не выделяя вторую матрицу.
4. Спиральная выдача#
Дан прямоугольный массив, представляющий слои коробок на складе. Выведите элементы по часовой спирали, начиная с верхнего левого угла и двигаясь вправо. Каждый элемент должен появиться ровно один раз, включая матрицы из одной строки или одного столбца.
Ввод: R C (1 ≤ R,C ≤ 1000), затем матрица целых чисел (|a[r][c]| ≤ 10^9).
Вывод: все элементы в порядке спирального обхода.
Пример:
3 4
1 2 3 4
5 6 7 8
9 10 11 12
1 2 3 4 8 12 11 10 9 5 6 7
Требование: O(R*C) времени и O(1) дополнительной памяти сверх матрицы. Поддерживайте четыре границы непройденной области и аккуратно проверяйте, что после сужения границ остались строки или столбцы.