Двумерные массивы

Упражнения

Общие требования к оформлению программ.

Если в задании дан массив, то считывание данных осуществляется функцией void read(vector<vector<int> > & A). Эта функция считывает размеры массива, меняет размер переданного по ссылке массива, заполняет его считанными значениями.

Решение задачи осуществляется функцией, получающей массив по ссылке в качестве параметра. Запрещен вывод результата из этой функции. Вообще запрещён любой ввод-вывод данных из этой функции.

Вывод массива на экран осуществляется отдельной функцией print, получающей в качестве параметра массив по ссылке.

Типичный вид программы на примере задачи G:

void read(vector<vector<int> > & A)
{
    ...
}

void swap_diagonals(vector<vector<int> > & A)
{
    ...
}

void print(vector<vector<int> > & A)
{
   ...
}

int main()
{
    vector<vector<int> > A;
    read(A);
    swap_diagonals(A);
    print(A);
    return 0;
}

От этой схемы могут быть отклонения, т.к. в некоторых задачах отсутствует ввод или вывод массива. Отдельные числа, например, размер массива если массив не дан, или результат работы программы, если он является одним числом, можно осуществлять из функции main, а не из специальных функций.

A: Максимум

Найдите индексы первого вхождения максимального элемента. Выведите два числа: номер строки и номер столбца, в которых стоит наибольший элемент в двумерном массиве. Если таких элементов несколько, то выводится тот, у которого меньше номер строки, а если номера строк равны то тот, у которого меньше номер столбца.

Программа получает на вход размеры массива n и m, затем n строк по m чисел в каждой.

Ввод	Вывод
3 4 0 3 2 4 2 3 5 5 5 1 2 3	1 2

B: Шахматная доска

Даны два числа n и m. Создайте двумерный массив размером n×m элементов типа char и заполните его символами "." и "*" в шахматном порядке. В левом верхнем углу должна стоять точка.

Ввод	Вывод
3 4	. * . * * . * . . * . *

C: Диагонали параллельные главной

Дано число n. Создайте массив размером n×n и заполните его по следующему правилу. На главной диагонали должны быть записаны числа 0. На двух диагоналях, прилегающих к главной, числа 1. На следующих двух диагоналях числа 2, и т.д.

Ввод	Вывод
5	0 1 2 3 4 1 0 1 2 3 2 1 0 1 2 3 2 1 0 1 4 3 2 1 0

D: Побочная диагональ

Дано число n. Создайте массив размером n×n и заполните его по следующему правилу:

Числа на диагонали, идущей из правого верхнего в левый нижний угол равны 1.

Числа, стоящие выше этой диагонали, равны 0.

Числа, стоящие ниже этой диагонали, равны 2.

Полученный массив выведите на экран. Числа в строке разделяйте одним пробелом.

Ввод	Вывод
4	0 0 0 1 0 0 1 2 0 1 2 2 1 2 2 2

E: Поменять столбцы

Дан двумерный массив и два числа: i и j. Поменяйте в массиве столбцы с номерами i и j и выведите результат.

Программа получает на вход размеры массива n и m, затем элементы массива, затем числа i и j.

Решение оформите в виде функции void swap_columns(vector<vector<int> > & A, int i, int j).

Ввод	Вывод
3 4 11 12 13 14 21 22 23 24 31 32 33 34 0 1	12 11 13 14 22 21 23 24 32 31 33 34

F: Симметричен ли массив?

Дано число n и массив размером n×n. Проверьте, является ли этот массив симметричным относительно главной диагонали. Выведите слово “YES”, если массив симметричный, и слово “NO” в противном случае.

Решение оформите в виде функции bool is_symmetric (vector<vector<int> > & A).

Ввод	Вывод
3 0 1 2 1 2 3 2 3 4	YES

G: Поменять две диагонали

Дан квадратный массив. Поменяйте местами элементы, стоящие на главной и побочной диагонали, при этом каждый элемент должен остаться в том же столбце (то есть в каждом столбце нужно поменять местами элемент на главной диагонали и на побочной диагонали).

Ввод	Вывод
3 1 2 3 4 5 6 7 8 9	7 2 9 4 5 6 1 8 3

H: k-я диагональ

Дан квадратный двумерный массив размером n×n и число k. Выведите элементы k-й по счету диагонали ниже главной диагонали (т.е. если k == 1, то нужно вывести элементы первой диагонали, лежащей ниже главной, если k == 2, то второй диагонали и т.д.).

Значение k может быть отрицательным, например, если k == -1, то нужно вывести значение первой диагонали лежащей выше главной. Если k == 0, то нужно вывести элементы главной диагонали.

Программа получает на вход число n, затем массив размером n×n, затем число k.

Решение оформите в виде функции void kth_diagonal(vector<vector<int> > & A, int k, vector<int> & res), где A — исходный массив, res — массив для записи результата. Сложность этой функции должна быть \(O(n - |k|)\) (число элементов на диагонали равно \(n-|k|\)), то есть в функции не должно быть переборов всех элементов массива вложенными циклами.

Ввод	Вывод
4 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 1	5 1 6
4 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 -2	3 8

I: Транспонировать прямоугольную матрицу

Дан двумерный массив размером n×m. Симметричный ему относительно главной диагонали массив называется транспонированным к данному. Он имеет размеры m×n: строки исходного массива становятся столбцами транспонированного, столбцы исходного массива становятся строками транспонированного.

Для данного массива постройте транспонированный массив и выведите его на экран. Решение оформите в виде функции void transpose(vector<vector<int> > & src, vector<vector<int> > & dst).

Ввод	Вывод
3 4 11 12 13 14 21 22 23 24 31 32 33 34	11 21 31 12 22 32 13 23 33 14 24 34

J: Транспонировать квадратную матрицу

Дан двумерный массив размером n×n. Транспонируйте его и результат запишите в этот же масссив. Вспомогательный массив использовать нельзя.

Решение оформите в виде функции void transpose(vector<vector<int> > & src).

Ввод	Вывод
3 1 2 3 4 5 6 7 8 9	1 4 7 2 5 8 3 6 9

Даны два числа n и m. Создайте массив n×m и заполните его по следующим правилам:

K: Число маршрутов короля

В левом верхнем углу доски размером n×m стоит шахматный король. За один ход он может сделать ход вправо, вниз или на одну клетку по диагонали вправо-вниз. Посчитайте количество маршрутов, ведущий из левого верхнего угла доски в правый нижний.

Программа получает на вход размеры доски (числа n и m) и должна вывести число искомых маршрутов.

Ввод	Вывод
3 4	25

L: Таблица умножения

Даны числа n и m. Создайте двумерый массив размером n×m и заполните его таблицей умножения по формуле A[i][j] = i * j.

При заполнении массива нельзя использовать вложенные циклы.

Выведите получившийся массив на экран (при выводе можно использовать вложенные циклы), отводя на вывод каждого числа ровно 4 символа (дополнительные пробелы между числами выводить не требуется, одна строка должна занимать ровно \(4m\) символов).

Ввод	Вывод
4 6	0 0 0 0 0 0 0 1 2 3 4 5 0 2 4 6 8 10 0 3 6 9 12 15

M: Одномерный массив в двумерный

Дан одномерный массив из \(n\times m\) элементов. Сделайте из него двумерный массив из \(n\) строк по \(m\) элементов в каждой.

Программа получает на вход числа \(n\) и \(m\). Во второй строке записано \(nm\) целых чисел через пробел.

Считайте данный массив. Затем создайте из него двумерный массив и выведите его в виде двумерной таблицы, разделяя элементы одним пробелом.

Решение оформите в виде функции, принимающей параметры (vector<int> src, int n, int m, vector<vector<int> > & dst).

Ввод	Вывод
2 5 0 1 2 3 4 5 6 7 8 9	0 1 2 3 4 5 6 7 8 9

N: Заполнение змейкой

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m “змейкой”, как показано в примере. Выведите полученный массив, отводя на вывод каждого элемента ровно 4 символа.

Решение оформите в виде функции void fill(vector<vector<int> > & res, int n, int m).

Ввод	Вывод
3 5	1 2 3 4 5 10 9 8 7 6 11 12 13 14 15

O: Заполнение диагоналями

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m “диагоналями”, как показано в примере. Выведите полученный массив, отводя на вывод каждого элемента ровно 4 символа.

Ввод	Вывод
3 5	1 2 4 7 10 3 5 8 11 13 6 9 12 14 15

P: Поворот прямоугольного массива

Дан прямоугольный массив размером n×m. Поверните его на 90 градусов по часовой стрелке, записав результат в новый массив размером m×n.

Выведите получившийся массив. Числа при выводе разделяйте одним пробелом.

Решение оформите в виде функции void rotate(vector<vector<int> > & src, vector<vector<int> > & dst).

Ввод	Вывод
3 4 11 12 13 14 21 22 23 24 31 32 33 34	31 21 11 32 22 12 33 23 13 34 24 14

Q: Поворот квадратного массива

Дан квадратный массив. Поверните его на 90 градусов по часовой стрелке. Результат запишите в этот же массив, вспомогательный массив использовать нельзя.

Выведите результат на экран, разделяя числа одним пробелом.

Решение оформите в виде функции void rotate(vector<vector<int> > & src).

Ввод	Вывод
3 1 2 3 4 5 6 7 8 9	7 4 1 8 5 2 9 6 3

R: Заполнение в шахматном порядке

Даны числа n и m. Заполните массив размером n×m в шахматном порядке: клетки одного цвета заполнены нулями, а другого цвета - заполнены числами натурального ряда сверху вниз, слева направо. В левом верхнем углу записано число 1.

Выведите полученный массив на экран, отводя на вывод каждого элемента ровно 4 символа.

Ввод	Вывод
3 5	1 0 2 0 3 0 4 0 5 0 6 0 7 0 8

S: Ходы коня

Дана шахматная доска из \(N\) строк и \(M\) столбцов. На ней стоит \(K\) шахматных коней. Постройте изображение доски, отметив на ней коней и клетки, которые бьют кони.

Клетку, где стоит конь, отметьте буквой “K”, клетки, которые бьет конь (но в ней нет коня), отметьте символами “*”, остальные клетки заполните точками.

Первая строка входных данных содержит три числа \(N\), \(M\), \(K\): количество строк доски, количество столбцов в доске и количество коней на доске (\(1\le N\le 300\), \(1\le M\le 300\), \(0\le K \le 10000\)).

В следующих \(K\) строках содержатся координаты коней по два числа \(x_i\), \(y_i\) (\(0\le x_i\lt N\), \(0\le y_i\lt M\)), номер строки и номер столбца очередного коня соответственно (нумерация с нуля сверху вниз, слева направо).

Выведите на экран изображение доски, разделяя символы в строке пробелами.

Решение должно иметь сложность \(O(NM + K)\), решение сложности \(O(NMK)\), то есть перебирающее все клетки доски, и для каждой клетки перебирающее всех коней, не пройдет по времени.

Чтобы не перебирать все возможные ходы коня “ручным” разбором случаев:

const int DX[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int DY[] = {2, -2, 2, -2, 1, -1, 1, -1};

Ввод	Вывод
4 7 2 1 1 3 6	. . . * . . . . K . . . * . . . . * * . . * . * . . . K
3 3 2 1 0 2 2	. * * K . . . . K

T: Ходы ферзя

Решите предыдущую задачу для ферзя. Ферзь обозначается буквой “Q”. Требуемая сложность алгоритма: \(O(NM + K(N + M))\).

Ввод	Вывод
4 7 1 1 1	* * * . . . . * Q * * * * * * * * . . . . . * . * . . .
3 3 2 0 0 2 0	Q * * * * . Q * *

U: Кинотеатр

В кинотеатре n рядов по m мест в каждом. В двумерном массиве хранится информация о проданных билетах, число 1 означает, что билет на данное место уже продано, число 0 означает, что место свободно. Поступил запрос на продажу k билетов на соседние места в одном ряду. Определите, можно ли выполнить такой запрос.

Программа получает на вход числа n и m. Далее идет n строк, содержащих m чисел (0 или 1), разделенных пробелами. Затем дано число k.

Программа должна вывести номер ряда, в котором есть k подряд идущих свободных мест. Если таких рядов несколько, то выведите номер наименьшего подходящего ряда. Если подходящего ряда нет, выведите число 0.

Ввод	Вывод
3 4 0 1 0 1 1 0 0 1 1 1 1 1 2	2
3 3 0 1 0 1 0 0 1 1 1 3	0

V: Заполнение спиралью

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m по спирали, выходящей из левого верхнего угла и закрученной по часовой стрелке, как показано в примере. Выведите полученный массив, отводя на вывод каждого элемента ровно 4 символа.

Тесты к этой задаче закрытые.

Ввод	Вывод
4 5	1 2 3 4 5 14 15 16 17 6 13 20 19 18 7 12 11 10 9 8

W: Домино

Проводя генеральную уборку на дачном чердаке, Саша нашел в комоде кучу доминошек из разных наборов. Каждая доминошка представляет собой прямоугольник, разделенный на две половинки. На каждой из половинок нарисовано от 0 до 6 точек. Ориентации доминошки не имеют — их можно как угодно поворачивать.

В совсем раннем детстве Саша видел, как играют в домино: суть игры заключается в том, что надо брать доминошку и как можно громче колотить ею об стол, крича при этом «рыба!». Услышав доносящийся с чердака грохот, наверх поднялся Сашин дедушка. Он смог объяснить Саше настоящие правила игры в домино: игроки составляют длинную цепочку, в которой соседние доминошки касаются половинками с одинаковым числом точек.

Саше решил называть «дружными доминошками» пару доминошек, которые можно поставить в игре рядом (т.е. доминошки в паре соприкасаются половинками с равными числами) в том или ином порядке. Играть в домино ему не с кем, поэтому Саша развлекается тем, что всевозможными способами составляет пары и считает количество «дружных доминошек».

По заданному набору доминошек определите, сколько пар «дружных доминошек» можно составить из него. Пары, отличающиеся хотя бы одной доминошкой, считаются различными. По-разному составленная пара из одних и тех же доминошек считается один раз.

В первой строке входного файла содержится натуральное число \(N\) — количество доминошек (\(1 \le N ≤ 100000\)).

В каждой из последующих строк содержится описание доминошки: два целых числа \(X\) и \(Y\) (\(0 \le X, Y \le 6\)) — количество точек на каждой из половинок доминошки.

Выведите одно число — количество пар «дружных доминошек».

Ввод	Вывод
2 1 2 2 1	1
5 1 2 2 3 3 1 4 3 4 3	8

Примечание. Во втором тесте дружными являются следующие пары: 1-2 2-3, 1-2 3-1, 2-3 3-1, 2-3 4-3, 2-3 4-3, 3-1 4-3, 3-1 4-3, 4-3 4-3

X: Покер-3

\(K\) человек играют в покер по правилам, описанным в задании предыдущего листка. Каждый получает на руки \(N\) карт возможных значений от \(1\) до \(N\).

Пронумеруем игроков числами от 1 до \(K\). Упорядочите их по невозрастанию силы комбинации их карт, а при одинаковой силе комбинаций — по возрастанию номера игрока.

По значениям карт двух игроков определите, кто выигрывает.

Первая строка входных данных содержит числа \(K\) и \(N\) — количество игроков и количество карт на руках у каждого из них, \(1\le K\times N\le 10^5\). Следующие \(K\) строк содержат по \(N\) натуральных чисел от 1 до \(N\) каждое — значения карт каждого игрока.

Программа должна вывести перестановку чисел 1, ..., \(K\).

Ввод	Вывод
5 4 3 2 1 4 2 3 3 3 1 1 2 2 1 1 2 1 2 1 3 2	2 4 3 5 1

Y: “Магический” квадрат

Заполните квадратную таблицу \(N\times N\) нулями и единицами так, чтобы в любом квадрате размером \(K\times K\) было ровно \(S\) единиц.

Программа получает на вход числа \(N\), \(K\), \(S\) (\(1\le N\le 100\), \(1\le K\le N\), \(0\le K\le S^2\)).

Выведите полученную таблицу, разделяя числа пробелами. Если решений несколько, можно вывести любое из них.

Ввод	Вывод
3 2 1	0 0 0 0 1 0 0 0 0
4 2 2	1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0

Z: Жизнь

Наиболее известный пример клеточного автомата — игра “Жизнь” — устроен по следующим правилам. В каждой клетке клетчатого поля может жить микроорганизм. Для клетки подсчитывается количество соседних с ней клеток (по стороне или по углу), в которых есть микроорганизмы.

Все микроорганизмы, у которых менее двух соседей, умирают от скуки.
Все микроорганизмы, у которых более трех соседей, умирают от перенаселенности.
В пустых клетках, у которых ровно три живых соседа, появляется новый микроорганизм.

Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках. Можно считать, что каждую секунду происходит обновление всех клеток по указанным правилам. Требуется по данной конфигурации определить, во что она превратится через T секунд.

В первой строке входных данных записаны два натуральных числа — размер квадратного поля \(N\) (\(1 \le N \le 10\)) и время \(T\) (\(1 \le T \le 100\)). Далее записано \(N\) строк по \(N\) чисел, описывающих начальную конфигурацию (0 — пустая клетка, 1 — микроорганизм). Числа в строках разделены пробелами.

Необходимо вывести \(N\) строк по \(N\) чисел — описание конфигурации через \(T\) секунд.

Ввод	Вывод
3 1 1 0 1 1 0 1 1 0 1	0 0 0 1 0 1 0 0 0
2 2 1 1 1 1	1 1 1 1
5 10 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0	0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0