Двумерные массивы в C++#

Матрица — таблица значений с индексами строки и столбца. Примеры из жизни: расписание уроков, игровое поле, карта высот и пиксели изображения. В задаче матрица размера rows × cols содержит rows строк и cols столбцов; индексы начинаются с нуля.

Простое представление: вектор векторов#

int rows, cols;
std::cin >> rows >> cols;
std::vector<std::vector<int>> a(rows, std::vector<int>(cols));
for (int r = 0; r < rows; ++r)
    for (int c = 0; c < cols; ++c)
        std::cin >> a[r][c];

Обращение a[r][c] читается как «строка r, столбец c». Для квадратной матрицы rows == cols, для прямоугольной — размеры могут отличаться. Нельзя предполагать квадратность, если это не сказано в условии. Вложенный вектор позволяет строкам иметь разную длину, но каждая внутренняя строка — отдельный vector, поэтому вся матрица не обязательно лежит в одном непрерывном блоке памяти.

Плоское хранение#

Для прямоугольной матрицы можно хранить значения в одном векторе длины rows * cols. Элемент (r,c) лежит по индексу r * cols + c:

std::vector<int> a(static_cast<std::size_t>(rows) * cols);
a[static_cast<std::size_t>(r) * cols + c] = value;

Это хранение единым буфером: удобно для больших матриц и алгоритмов, которым важна непрерывность памяти. Формула использует число столбцов, не строк. Прежде чем выделять память, проверьте допустимость размеров и риск переполнения при их перемножении.

Обходы#

Обычный обход по строкам:

for (int r = 0; r < rows; ++r) {
    for (int c = 0; c < cols; ++c) {
        // обработать a[r][c]
    }
}

Так элементы читаются в естественном для C++ порядке хранения. Сумма всех элементов стоит O(rows * cols). Обход соседей клетки используйте только после проверки границ: 0 <= nr < rows и 0 <= nc < cols. Для направлений часто заводят массивы dr = {-1, 1, 0, 0} и dc = {0, 0, -1, 1}.

Память и алгоритмическая сложность#

Матрица из R*C значений занимает O(R*C) памяти. Если задачу можно решить построчно, храните только необходимые строки — иногда дополнительную память удаётся уменьшить с O(R*C) до O(C). Например, при вычислении каждой строки динамического программирования могут быть нужны только предыдущая и текущая строки. Различайте память самой входной матрицы и дополнительную память алгоритма.

Поворот или транспонирование матрицы обычно требуют либо нового буфера O(R*C), либо аккуратных операций на месте. Квадратную матрицу можно транспонировать на месте, меняя местами a[r][c] и a[c][r] только для c > r. Для прямоугольной матрицы размеры меняются местами, поэтому простое такое правило не подходит.

Сравнение языков#

Python часто представляет таблицу как список списков: grid[r][c]. Создавая матрицу, не используйте [[0] * cols] * rows: все строки окажутся ссылками на один и тот же список. Используйте [[0 for _ in range(cols)] for _ in range(rows)].

Rust обычно использует Vec<Vec<T>> или плоский Vec<T> с индексом r * cols + c. Как и в C++, вложенные векторы удобны для строк, а плоский буфер — для одного непрерывного блока. Rust дополнительно проверяет владение и заимствования; C++ программист сам отвечает за границы и время жизни ссылок. У vector<vector<T>> внешний vector владеет строками, у плоского vector — единым хранилищем.

Частые ошибки#

• Перепутаны rows и cols, особенно при транспонировании.
• Цикл идёт до <= rows вместо < rows.
• Индекс вычислен как c * rows + r, хотя правильная формула для построчного хранения — r * cols + c.
• Доступ к соседу происходит до проверки его координат.
• Создана матрица с rows * cols, но произведение переполнилось или объём слишком велик.
• В Python строки матрицы случайно разделяют один список.