Двумерные массивы - Язык программирования C++ для спортивного программирования
Неделя 6Вложенные циклы, Двумерные массивы и Задачи на сетках
Двумерные массивы
Таблица как вектор векторов: a[i][j] — строка i, столбец j; чтение и печать строка за строкой; углы, центр, строка, столбец и край; проходы по всей таблице — по строкам и по столбцам; две диагонали и симметрия; обмен целых строк; новые таблицы из старых — поворот и отражение; зигзаг, змейка и спираль.
Теория
Урок 5 из 11
17 мин чтения
Вопросов: 6
В уроке Вложенные циклы циклы печатали таблицы. Часто таблица — это ввод:
продажи кафе за каждый день по каждому напитку, оценки каждого ученика по
каждому предмету, пиксели фотографии. Вектор хранит одну строку чисел; чтобы
хранить целую таблицу, со строками и столбцами, нужен двумерный массив.
Таблица — это вектор векторов
Читайте изнутри наружу: vector<int>(m) — одна строка из m нулей, а a —
вектор из n таких строк. Значит, a[i] — строка i (сама по себе вектор), а
a[i][j] — элемент в строке i, столбце j. Оба индекса начинаются с 0:
столбец 0
столбец 1
столбец 2
строка 0
a[0][0]
a[0][1]
a[0][2]
строка 1
a[1][0]
a[1][1]
a[1][2]
Сначала строка, потом столбец — этот порядок нужно запомнить. a.size() —
число строк n, а a[i].size() — длина строки m. Каждое a[i][j] — обычный
int: его можно читать, печатать, менять и сравнивать. Для значений, которые
растут, например сумм, используйте vector<vector<long long>>.
Чтение и печать таблицы
Во вводе таблица идёт строка за строкой, слева направо — ровно в порядке двух
вложенных циклов:
дальше
Практика: Клетки, Строки и Столбцы
Прочитайте таблицу, а потом используйте одну её клетку, одну строку или один столбец.
Печать — те же циклы с cout и переводом строки после каждой строки.
Вложенные циклы обходят клетки строка за строкой: всю строку 0, потом всю
строку 1 и так далее. Если нумеровать посещения с 0, посещение номер k — это
клетка в строке k / m, столбце k % m: при m = 4 посещение 6 — строка 1,
столбец 2.
В условиях строки и столбцы обычно нумеруются с 1. Как и с векторами,
клетка (r, c) из условия — это a[r - 1][c - 1].
Одна клетка, одна строка, один столбец
Когда таблица прочитана, любая клетка достаётся одним обращением, где бы она ни
стояла:
Строка — это цикл по индексу столбца при фиксированном номере строки, а столбец —
цикл по индексу строки при фиксированном номере столбца:
Строка — это вектор, поэтому две строки целиком можно поменять за один шаг:
swap(a[p], a[q]); меняет местами строки p и q со всеми их элементами.
Проходы по всей таблице
Суммы, количества, наибольшее и наименьшее из Недели 4 работают по всем
клеткам: два вложенных цикла вместо одного. С суммами осторожно: таблица
100 × 100 из чисел до 10⁹ даёт в сумме до 10¹³ — long long.
Часто вопрос задаётся про каждую строку отдельно: сумма каждой строки,
наибольшее в каждой строке, возрастает ли каждая строка? Тогда переменная для
строки объявляется внутри внешнего цикла, чтобы для каждой строки она
начиналась заново:
Строка за строкой: новая сумма для каждой строки
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<vector<int>> a = {{3, 8, 1}, {5, 0, 6}};
9 int n = 2, m = 3;
10 for (int i = 0; i < n; i++) {
11 long long s = 0;
12 for (int j = 0; j < m; j++) {
13 s += a[i][j];
14 }
15 cout << s << "\n";
16 }
17 return 0;
18}
Таблица из 2 строк
строка 8
a[0] — строка 3 8 1, a[1] — строка 5 0 6. a[i][j] — строка i, столбец j.
a2×3
0
1
2
0
3
8
1
1
5
0
6
n—m—i—s—j—
нажми пуск
1 / 34
Для каждого столбца поменяйте циклы местами: внешний идёт по столбцам j,
внутренний — по строкам i. Одна программа может сделать и то и другое:
Кафе хранит продажи в таблице: n дней и для каждого дня число проданных
чашек каждого из m напитков. Выведите итог каждого дня, а затем итог
каждого напитка.
Ввод
Вывод
Чтобы найти, какая строка лучшая — день с наибольшими продажами, —
посчитайте сумму каждой строки и храните лучшую сумму и номер её строки, как
best хранил индекс в Неделе 4. С > из равных строк побеждает первая. Вопрос
о соседях в строке (возрастает ли строка?) сравнивает a[i][j - 1] с a[i][j]
внутри строки, а переменная bool в начале каждой строки получает true.
Теперь поработайте с таблицей кафе сами: нажмите на клетки, которые использует
каждый кусок кода.
Неделя в кафепопробуй!
Диагонали и симметрия
В квадратной таблице n × nглавная диагональ идёт из левого верхнего
угла в правый нижний: это клетки a[i][i]. Побочная диагональ идёт из
правого верхнего угла в левый нижний: в строке i она в столбце n - 1 - i.
Каждая — это один цикл:
Когда n нечётное, центральная клетка лежит на обеих диагоналях и входит в
обе суммы. (Если считать с 1, как во многих условиях, побочная диагональ — это
клетки, где i + j == n + 1.)
Таблица симметрична относительно главной диагонали, если каждая клетка равна
своему отражению: a[i][j] == a[j][i] для всех i и j. Чтобы ответить «нет»,
достаточно одной неравной пары, поэтому начните с bool sym = true; и при первом
несовпадении сделайте её false.
Новые таблицы из старых: поворот и отражение
Поворот или отражение таблицы переносят каждый элемент на новое место.
Выясните, куда попадает элемент строки i, столбца j, а затем либо постройте
новую таблицу, либо просто печатайте в новом порядке.
Новая таблица
Элемент a[i][j] попадает в
Размер
отражённая слева направо
строку i, столбец m - 1 - j
n × m
отражённая сверху вниз
строку n - 1 - i, столбец j
n × m
повёрнутая на 90° по часовой стрелке
строку j, столбец n - 1 - i
m × n
повёрнутая на 90° против часовой стрелки
строку m - 1 - j, столбец i
m × n
У повёрнутой таблицы m строк и n столбцов: строки и столбцы меняются ролями.
Чтобы её напечатать, каждая печатаемая строка — это столбец старой таблицы,
прочитанный в нужном направлении:
Фотография — это n строк по m чисел. Выведите её повёрнутой на 90° против
часовой стрелки.
Ввод
Вывод
Первая печатаемая строка — последний столбец старой таблицы, прочитанный
сверху вниз. При повороте по часовой стрелке первая печатаемая строка — первый
столбец, прочитанный снизу вверх.
Зигзаги, змейки и спирали
В некоторых ответах таблица обходится в необычном порядке.
Зигзаг: строка 0 слева направо, строка 1 справа налево и так далее.
Проверяйте номер строки: if (i % 2 == 0) — j растёт от 0, else —
убывает от m - 1.
Змейка по столбцам: то же самое, только роли поменялись — заполняйте или
печатайте столбец за столбцом, вниз в чётных столбцах и вверх в нечётных.
Счётчик, объявленный до циклов, нумерует клетки в том порядке, в каком до них
доходит обход.
Спираль: по внешнему кольцу по часовой стрелке, потом по внутреннему, пока
не будут напечатаны все клетки. Храните четыре границы — первую и последнюю
ещё не напечатанные строку и столбец — и сдвигайте каждую внутрь, пройдя её:
20 for (int i = bottom; i >= top; i--) cout << a[i][left] << " ";
21 left++;
22 }
23 }
24 cout << "\n";
25 return 0;
26}
Таблица 3 × 3
строка 8
Числа расставлены так, что по спирали они читаются от 1 до 9.
a3×3
0
1
2
0
1
2
3
1
8
9
4
2
7
6
5
top—bottom—left—right—j—i—
нажми пуск
1 / 40
Два if важны, когда таблица не квадратная: если верхняя граница уже прошла
нижнюю (или левая — правую), эта строка или столбец уже напечатаны. Без проверок
таблица из одной строки 1 2 3 вышла бы как 1 2 3 2 1.
Двумерные массивы фиксированного размера
Во многих решениях, которые вы встретите, вместо вектора — обычный массив:
Его делают размером с самую большую таблицу из условия плюс несколько запасных
клеток и используют только первые n строк и m столбцов. Если в каком-то тесте
таблица окажется больше, чем обещало условие, программа выйдет за границы
массива; вектор векторов, созданный по настоящим n и m, всегда подходит по
размеру. В этом курсе мы используем
vector<vector<int>>.
Проверьте себя
А вы знали?
Первая программа электронных таблиц для персональных компьютеров, VisiCalc,
вышла в 1979 году для Apple II. Её авторы, Дэн Бриклин и Боб Франкстон,
построили её вокруг той же идеи: сетка клеток, у каждой — строка и столбец, и
итоги строк и столбцов, которые пересчитываются, когда меняется число. Многие
покупали Apple II только ради неё.
vector<vector<int>> a(n, vector<int>(m));
проверь себя1 балл
Что напечатает этот код?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Таблицу из 3 строк и 5 столбцов поворачивают на 90° по часовой стрелке. Куда попадёт её правый верхний элемент a[0][4]?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В таблице 3 строки и 5 столбцов. Два вложенных цикла (снаружи — строки, внутри — столбцы) обходят её клетки, а посещения нумеруются с 0. Какая клетка будет посещением 7?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
a — таблица n × m. Какой цикл печатает столбец c сверху вниз?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Таблица — {{1, 2}, {3, 4}}. Что напечатает этот код?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
a — таблица n × n, индексы с 0. Какая клетка строки i лежит на побочной диагонали — из правого верхнего угла в левый нижний?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
3 4
12 30 5 8
10 26 9 11
14 35 7 6
55 56 62
36 91 21 25
2 3
7 1 4
9 8 2
4 2
1 8
7 9
int n, m;cin >> n >> m;vector<vector<int>> a(n, vector<int>(m));for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j];}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)); // n строк по m чисел for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j];}} for(int i = 0; i < n; i++){ // каждая строка — один день long long s = 0; // новая сумма для каждой строки for(int j = 0; j < m; j++){ s += a[i][j];} cout << s << " ";} cout << "\n"; for(int j = 0; j < m; j++){ // каждый столбец — один напиток long long s = 0; for(int i = 0; i < n; i++){ // теперь меняется i, а j стоит на месте s += a[i][j];} cout << s << " ";} cout << "\n"; return 0;}
long long mainSum = 0, antiSum = 0;for(int i = 0; i < n; i++){ mainSum += a[i][i]; antiSum += a[i][n - 1 - i];}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j];}} // у повёрнутого фото m строк и n столбцов for(int j = m - 1; j >= 0; j--){ // его первая строка — последний столбец for(int i = 0; i < n; i++){ // читаем сверху вниз cout << a[i][j]<< " ";} cout << "\n";} return 0;}
int a[105][105]; // вне main, как в Неделе 4int main(){ // ... a[i][j] работает точно так же, как у вектора векторов}
vector<vector<int>> a ={{1, 2, 3},{4, 5, 6}};cout << a[1][2];
long long s = 0;for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ s += a[i][j];} cout << s << " ";}