К содержанию

Анатолий
Анатольевич
Eфремов

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


Хранение матриц

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


Пример:

Если требуется создать числовую таблицу из двух строк и трёх столбцов, то это можно сделать следующим образом:

a = [[2, 3, 4], [5, 6, 7]]

Здесь первый элемент списка a[0] является списком из чисел [2, 3, 4]. То есть a[0][0] равно 2, a[0][1] равно 3, a[0][2] равно 4. Таким образом, чтобы обратиться к элементу, расположенному в i-й строке и j-м столбце, то надо написать a[i][j]. Также можно использовать отрицательные индексы, например, элемент a[-1][-1] нашей таблицы — это элемент из последней строки и последнего столбца, и он равен числу 7.


Обработка и вывод списка

Для обработки и вывода списка, как правило, используются два вложенных цикла. Первый цикл перебирает все строки, второй цикл — элементы внутри строки. Например, вывести двумерный числовой список на экран построчно, разделяя числа пробелами внутри одной строки, можно так:

for i in range(len(a)):
     for j in range(len(a[i])):
          print(a[i][j], end=' ')
     print()

Обратим внимание на то, что пробелы будут выведены не только между числами в строке, но и после последнего элемента. При сдаче задач эти пробелы не мешают, поэтому можно об этом не беспокоиться.

Можно перебирать элементы списка не по индексу, а по значению. Тогда код вывода двумерного массива будет иметь вот такой вид:

for row in a:
     for elem in row:
          print(elem, end=' ')
     print()

Кроме того, для вывода одной строки можно воспользоваться методом join:

for row in a:
     print(' '.join(list(map(str, row))))

Наконец, можно использовать и упрощенный способ вывода списков:

for i in range(len(a)):
     print(*a[i])


Пример:

Используем два вложенных цикла для подсчета суммы всех чисел в таблице и нахождения минимального элемента в таблице:

S = 0
M = a[0][0]
for i in range(len(a)):
     for j in range(len(a[i])):
          S += a[i][j]
          M = min(M, a[i][j])
print(S, M)


Для решения этой задачи можно использовать циклы не по индексам, а по элементам:

S = 0
M = a[0][0]
for row in a:
     for elem in row:
          S += elem
          M = min(M, elem)
print(S, M)


Заметим, что если мы хотим параллельно изменять значения элементов в нашей таблице, то придётся использовать первый вариант. Действительно, переменная elem является дополнительной переменной, и если мы ее меняем, то элемент таблицы при этом не меняется. Таким образом, если мы хотим не только найти сумму чисел и минимум исходной таблицы, но и увеличить все элементы таблицы на 1, то для этого надо использовать первый вариант, и код будет выглядеть следующим образом:

S = 0
M = a[0][0]
for i in range(len(a)):
     for j in range(len(a[i])):
          S += a[i][j]
          M = min(M, a[i][j])
          a[i][j] += 1
print(S, M)



Создание вложенных списков



Копирование списков

Научимся копировать списки в языке Python. Пусть у нас есть список a = [2, 3, 4]. Оказывается, что операция b = a не создаёт новый список. Такая операция делает имя b ссылкой на тот же список, на который ссылается имя a. Таким образом, a и b — это два разных имени, ссылающиеся на один список. Поэтому если мы модифицируем список a, например, добавив число 5 в конец списка: a.append(5), то модифицируется и список b.

Нам же нужно выполнить такую операцию, чтобы имя b ссылалось на список, который является копией списка a, а не на сам список a. Для этого можно использовать присваивание с использованием среза:
b = a[:].
Также можно использовать генератор:

b = [elem for elem in a].


Если есть необходимость создать копию двумерного списка, то возникают дополнительные сложности. Чтобы их избежать, рекомендуется выполнять копирование с использованием специальных функций из модуля copy. Подключить модуль copy можно, написав from copy import * в начале программы.


Создание двумерных списков

Пусть теперь нам нужно создать двумерный список из 3 строк и 4 столбцов, заполненный нулями. Кажется, что такой двумерный список можно создать следующим образом: a = [[0] * 4] * 3. Но тут возникает проблема. При таком способе a[0], a[1] и a[2] являются ссылками на один и тот же список [0] * 4. Поэтому после операции a[0][0] = 1, окажется, что элементы a[1][0] и a[2][0] тоже стали равны числу 1.

Чтобы правильно создать двумерный список, заполненный нулями и состоящий из n строк и m столбцов, необходимо, чтобы каждая строка списка создавалась заново. Есть несколько способов сделать это.


Например, можно создать список из n нулей, а затем каждый элемент этого списка заменить на список из m нулей. Во время замены список из m нулей будет создаваться заново, поэтому каждая из n строк окажется ссылкой на свой независимый список из m нулей:

a = [0] * n
for i in range(n):
     a[i] = [0] * m


Можно создать изначально пустой список, а потом n раз добавить в конец этого списка новый элемент, который является списком из m нулей:

a = []
for i in range(n):
     a.append([0] * m)


Также для создания двумерного списка можно использовать генератор, который создает список из n элементов, каждый из которых будет списком, состоящим из m нулей (подробнее о генераторах списков будет рассказано в следующем модуле):

a = [[0] * m for i in range(n)]


В каждом из этих трёх способов очередная строка создается независимо от остальных: заново конструируется список [0] * m, а не копируются ссылки на один и тот же список.



Задача 1

Снежинка

Дано нечётное число n. Создайте двумерный массив из n x n элементов, заполнив его символами «.» (каждый элемент массива является строкой из одного символа). Затем заполните символами «∗» среднюю строку массива, средний столбец массива, главную диагональ и побочную диагональ. Для этого не нужно использовать вложенные циклы.

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

Входные данные

В одной строчке задано число n ⩽ 21.

Выходные данные

Ответ на задачу.

Примеры

Ввод Вывод
5 * . * . *
. * * * .
* * * * *
. * * * .
* . * . *

ОТВЕТ:
n = int(input())
a = [["."] * n for i in range(n)]
for i in range(n):
     a[i][i] = "*"
     a[n - 1 - i][i] = "*"
     a[i][n // 2] = "*"
     a[n // 2][i] = "*"
print('\n'.join([' '.join([str(i) for i in row]) for row in a]))



Задача *

Ходы коня

На шахматной доске стоит конь. Отметьте положение коня на доске и все клетки, которые он бьёт. Клетку, где стоит конь, отметьте английской буквой «K». Клетки, которые он бьёт, отметьте символами «*». Остальные клетки заполните точками.

Входные данные

Программа получает на вход два числа — координаты коня на шахматной доске. Координаты вводятся на одной строке через пробел. Первое число обозначает номер строки, а второе — номер столбца. Все числа принимают значения от 1 до 8.

Выходные данные

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

Примеры

Ввод Вывод
4 2 . . . . . . . .
* . * . . . . .
. . . * . . . .
. K . . . . . .
. . . * . . . .
* . * . . . . .
. . . . . . . .
. . . . . . . .

Видеоразбор

ОТВЕТ:
ki, kj = map(int, input().split())
b = [['.'] * 12 for i in range(12)]
moves = [[1,2], [1,-2], [-1,2], [-1,-2], [2,1], [2,-1], [-2,1], [-2,-1]]
ki += 1
kj += 1
for di, dj in moves:
     i = ki + di
     j = kj + dj
     b[i][j] = '*'
b[ki][kj] = 'K'
for row in b[2:-2]:
     print(' '.join(row[2:-2]))



Считывание



Считывание двумерных массивов

Пусть программа получает на вход двумерный массив, состоящий из n строк и m столбцов. Научимся считывать такой массив.

Обычно в задачах нам сначала дают два числа n и m — размеры массива, а затем дают n строк, в каждой из которых записаны по m чисел, разделённых пробелами. Пример входных данных:

3 4
1 2 3 4
2 3 4 5
3 4 5 6

Сначала считаем два числа n и m, задающие размеры двумерного массива. После этого создадим пустой список a и повторим n раз следующую последовательность действий: считаем очередную строку из чисел, превратим строку в список из m чисел, разбив её по пробелам и преобразовав элементы к типу int, добавим полученный список в конец списка a.

n, m = map(int, input().split())
a = []
for i in range(n):
     a.append(list(map(int, input().split())))


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

Можно организовать считывание при помощи генератора следующим образом:

n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]



Задача *

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

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

Входные данные

Программа получает на вход в первой строке размеры массива n ⩽ 100 и m ⩽ 100, затем элементы массива, а в последней строке числа i и 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

Видеоразбор

ОТВЕТ:
n, m = map(int, input().split())
a = [input().split() for i in range(n)]
i, j = map(int, input().split())
for k in range(n):
     a[k][i], a[k][j] = a[k][j], a[k][i]
for row in a:
     print(' '.join(row))



Задача *

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

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

Входные данные

В первой строке дано значение n⩽10. Далее идут n строк по n чисел — элементы матрицы.

Выходные данные

Ответ на задачу.

Примеры

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

Видеоразбор

ОТВЕТ:
n = int(input())
a = [input().split() for i in range(n)]
ans = "YES"
for i in range(n):
     for j in range(i + 1, n):
          if a[i][j] != a[j][i]:
               ans = "NO"
print(ans)



Задача 2

Максимум

Найдите индексы первого вхождения максимального элемента в двумерном массиве.

Входные данные

Программа получает на вход размеры массива n ⩽ 10 и m ⩽ 10, затем n строк по m целых чисел, не превосходящих по модулю 231.

Выходные данные

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

Примеры

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

ОТВЕТ:
n, m = [int(i) for i in input().split()]
a = [[int(j) for j in input().split()] for i in range(n)]
max_i, max_j = 0, 0
c = a[0][0]
for i in range(n):
     for j in range(m):
          if a[i][j] > c:
               c = a[i][j]
               max_i, max_j = i, j
print(max_i, max_j)



Задача 3

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

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

Входные данные

В первой строке дано число n ⩽ 10. Далее идут n строк по n неотрицательных целых чисел не больше 100.

Выходные данные

Ответ на задачу.

Примеры

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

ОТВЕТ:
n = int(input())
a = [[int(elem) for elem in input().split()] for i in range(n)]
for i in range(n):
     a[i][i], a[n - i - 1][i] = a[n - i - 1][i], a[i][i]
for i in range(n):
     print(*a[i])



Задача 4

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

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

Входные данные

На первой строке входных данных задано натуральное число n ⩽ 500. В следующих n строках задано по n натуральных чисел — элементы массива.

Выходные данные

Выведите ответ на задачу.

Примеры

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

ОТВЕТ:
n = int(input())
a = [input().split() for i in range(n)]
for i in range(len(a)):
     for j in range(i, len(a)):
          a[i][j], a[j][i] = a[j][i], a[i][j]
for row in a:
     print(' '.join(row))



Задача 5

Треугольник Паскаля

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

  • Числа, стоящие в строке 0 или в столбце 0 равны 1 (A[0][j] = 1, A[i][0] = 1).
  • Для всех остальных элементов массива A[i][j] = A[i-1][j] + A[i][j-1], то есть каждый элемент равен сумме двух элементов, стоящих слева и сверху от него.

Входные данные

Вводятся два натуральных числа n и m, не превышающих 100.

Выходные данные

Выведите данный массив на экран.

Примеры

Ввод Вывод
3 3      1     1     1
     1     2     3
     1     3     6

Ввод Вывод
10 3      1     1     1
     1     2     3
     1     3     6
     1     4     10
     1     5     15
     1     6     21
     1     7     28
     1     8     36
     1     9     45
     1     10     55

ОТВЕТ:
n, m = map(int, input().split())
a = [[1] * m] * n
for i in range(m):
     print(a[0][i], end=' ')
print()
for i in range(n - 1):
     i += 1
     print(a[0][0], end=' ')
     for j in range(m - 1):
          j += 1
          a[i][j] = a[i][j - 1] + a[i - 1][j]
          print(a[i][j], end=' ')
     print()



Задача 6

Кинотеатр

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

Входные данные

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

Выходные данные

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

Примеры

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

ОТВЕТ:
n, m = map(int, input().split())
rows = [input() for i in range(n)]
k = int(input())
for i, row in enumerate(rows):
     if ' '.join("0" * k) in row:
          print(i + 1)
          break
else:
     print("0")



Задача 7

Золото

Мудрец ходит по комнате размера n x m клеток. В каждой клетке комнаты лежит заданное количество золота. Проходя по клетке мудрец забирает всё золото с неё. Зная план комнаты и маршрут мудреца, посчитайте сколько золота он собрал. В задаче не гарантируется, что мудрец не проходил по одной и той же клетке более одного раза.

Входные данные

Во входных данных описан план комнаты: сначала количество строк n, затем — количество столбцов m (1 ⩽ n ⩽ 20, 1 ⩽ m ⩽ 20). Затем записано n строк по m чисел в каждой — количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число x — сколько клеток обошел мудрец. Далее записаны координаты этих клеток (координаты клетки — это два числа: первое определяет номер строки, второе — номер столбца), верхняя левая клетка на плане имеет координаты (1,1), правая нижняя — (n,m).

Выходные данные

Выведите количество килограммов золота, которое собрал мудрец.

Примеры

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

ОТВЕТ:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
x = int(input())
s = 0
for i in range(x):
     s1, s2 = map(int, input().split())
     s += a[s1 - 1][s2 - 1]
     a[s1 - 1][s2 - 1] = 0
print(s)