К содержанию

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

Работа с двумерными массивами

Вложенные генераторы



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

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

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


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

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


Таким образом, мы получили два генератора, один из которых вложен в другой. Теперь, если в теле вложенного генератора вместо числа 0 записать какую-то формулу, зависящую от индексов i и j, то мы получим способ нетривиально заполнить наш двумерный массив. Ниже мы рассмотрим несколько примеров такого заполнения.


Пример 1

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

Для n = 3, m = 4 этот генератор заполнит двумерный массив следующим образом:
0 1 2 3
0 1 2 3
0 1 2 3


Пример 2

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

Для n = 3, m = 4 этот генератор заполнит двумерный массив так:
0 0 0 0
1 1 1 1
2 2 2 2


Пример 3

a = [[i + j for j in range(m)] for i in range(n)]

Для n = 3, m = 4 этот генератор заполнит двумерный массив следующим образом:
0 1 2 3
1 2 3 4
2 3 4 5


Пример 4

a = [[(int)(i == j) for j in range(m)] for i in range(n)]

В этом генераторе выражение (i == j) равно True, если элемент расположен на диагонали, и равно False в противном случае. Если преобразовать это выражение к целочисленному типу (int)(i == j), то в сгенерированной таблице на диагонали будут стоять единицы, а в остальных ячейках будут стоять нули.

Для n = 3, m = 4 этот генератор заполнит двумерный массив следующим образом:
1 0 0 0
0 1 0 0
0 0 1 0



Задача *

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

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

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

Вводится число n ⩽ 20.

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

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

Примеры

Ввод Вывод
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

Видеоразбор

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



Задача *

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

По данным числам n и m заполните двумерный массив размером n x m числами от 1 до n ⋅ m «змейкой», как показано в примере.

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

Вводятся два числа n ⩽ 40 и m ⩽ 40.

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

Выведите полученный массив.

Примеры

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

Видеоразбор

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



Задача 1

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

Даны два числа n и m. Создайте двумерный массив размером n x m и заполните его символами 1 и 0 в шахматном порядке. В левом верхнем углу должна стоять единица.

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

A = [текст генератора]

Примеры

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

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



Задача 2

Слева направо, сверху вниз

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

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

A = [текст генератора]

Примеры

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

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



Задача 3

Сверху вниз, слева направо

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

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

A = [текст генератора]

Примеры

Ввод Вывод
5 6 0 5 10 15 20 25
1 6 11 16 21 26
2 7 12 17 22 27
3 8 13 18 23 28
4 9 14 19 24 29

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



Задача 4

Квадранты

Дано число n. Создайте массив размером n x n и заполните его по следующему правилу. На главной и побочных диагоналях стоят нули, эти диагонали делят массив на четыре части. В верхней части записаны единицы, в правой записаны двойки, в нижней записаны тройки, в левой записаны четверки.

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

A = [текст генератора]

Примеры

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

ОТВЕТ:
n = int(input())
A = [[0 if i == j or i == n - j - 1 else
     1 if i < j < n - i - 1 else
     2 if i < j else
     3 if j > n - i - 1 else 4 for j in range(n)] for i in range(n)]
for i in range(n):
     for j in range(n):
          print(A[i][j], end = ' ')
     print()



Маршруты на клетчатом поле



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

Будем считать, что положение фишки задаётся парой чисел (i, j), где i — номер строки, а j — номер столбца. Строки нумеруются сверху вниз от 0 до n - 1, а столбцы — слева направо от 0 до m - 1. Таким образом, первоначальное положение фишки — клетка (0, 0), а конечное — клетка (n - 1, m - 1).

Пусть w(i, j) — количество маршрутов, ведущих в клетку (i, j) из начальной клетки. Запишем рекуррентное соотношение. В клетку (i, j) можно прийти двумя способами: из клетки (i, j - 1), расположенной слева, и из клетки (i - 1, j), расположенной сверху от данной. Поэтому количество маршрутов, ведущих в клетку (i, j), равно сумме количеств маршрутов, ведущих в клетку слева и сверху от неё. Получили рекуррентное соотношение:

w(i, j) = w(i, j - 1) + w(i - 1, j)

Это соотношение верно при i > 0 и j > 0. Зададим начальные значения: если i = 0, то клетка расположена на верхнем краю доски и прийти в неё можно единственным способом — двигаясь только вправо, поэтому w(0, j) = 1 для всех 0 ⩽ j < m. Аналогично, w(i, 0) = 1 для всех 0 ⩽ i < n.

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

В результате такого заполнения получим следующий массив (пример для n = 4, m = 5):

1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35

Код на языке Python, решающий эту задачу, будет выглядеть следующим образом:

n, m = map(int, input().split())
w = [[1] * m for i in range(n)]
for i in range(1, n):
     for j in range(1, m):
          w[i][j] = w[i][j - 1] + w[i - 1][j]
print(w[-1][-1])


Маршруты на клетчатом поле с дополнительными ограничениями

Теперь решим эту задачу с дополнительным ограничением — некоторые клетки таблицы запрещены для посещения фишкой. В этой задаче нам дополнительно даётся таблица t размера n на m состоящая из 0 и 1. Если t(i, j) = 0, то в клетку (i, j) перемещать фишку запрещено. Гарантируется, что t(0, 0) = 1.

Будем решать эту задачу аналогично предыдущей. Изменение состоит в том, что есть клетки, в которые мы не можем перемещать фишку. Формально можно записать, что если t(i, j) = 0, то w(i, j) = 0. Если же t(i, j) = 1, то w(i, j) = w(i, j - 1) + w(i - 1, j). Можно объединить эти два случая в одну формулу следующим образом:

w(i, j) = t(i, j) ⋅ (w(i, j - 1) + w(i - 1, j))


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

Код, решающий эту задачу, будет выглядеть следующим образом:

n, m = map(int, input().split())
t = [list(map(int, input().split())) for i in range(n)]
w = [[1] * m for i in range(n)]
for i in range(1, n):
     w[i][0] = t[i][0] * w[i - 1][0]
for j in range(1, m):
     w[0][j] = t[0][j] * w[0][j - 1]
for i in range(1, n):
     for j in range(1, m):
          w[i][j] = t[i][j] * (w[i][j - 1] + w[i - 1][j])
print(w[-1][-1])



Задача 5

Количество маршрутов в прямоугольной таблице

В прямоугольной таблице N x M вначале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку.

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

Вводятся два числа N и M — размеры таблицы 1 ⩽ N ⩽ 10, 1 ⩽ M ⩽ 10.

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

Выведите искомое количество способов.

Примеры

Ввод Вывод
1 10 1

ОТВЕТ:
from math import factorial
n, m = map(int, input().split())
n -= 1
m -= 1
ans = factorial(n + m) // (factorial(n) * factorial(m))
print(ans)



Задача *

Самый дешёвый путь

В каждой клетке прямоугольной таблицы N x M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

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

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

Вводятся два числа N и M — размеры таблицы 1 ⩽ N ⩽ 20, 1 ⩽ M ⩽ 20. Затем идёт N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

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

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

Примеры

Ввод Вывод
5 5
1 1 1 1 1
3 9 9 9 9
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
11

Видеоразбор

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



Задача 6

Шашку — в дамки

На шахматной доске (8 x 8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?

(Белая шашка ходит по диагонали: на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

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

Вводятся два числа от 1 до 8: номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

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

Вывести одно число — количество путей в дамки.

Примеры

Ввод Вывод
3 7 2

Ввод Вывод
1 8 1

Ввод Вывод
3 6 4

ОТВЕТ:
def cik(x, y):
     if x < 1 or x > 8:
          return 0
     if y == 8:
          return 1
     return cik(x - 1, y + 1) + cik(x + 1, y + 1)
x, y = map(int, input().split())
print(cik(x, y))



Задача 7

Вывести маршрут максимальной стоимости

В левом верхнем углу прямоугольной таблицы размером N x M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

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

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идут N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

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

Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N - 1 букву D, означающую передвижение вниз и M - 1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры

Ввод Вывод
5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9
74
D D R R R R D D

ОТВЕТ:
global n, m, zed, terra
def mp(x, y):
     try:
          return terra[x, y]
     except:
          if x > 0:
               left = mp(x - 1, y)
          else:
               left = (-1, [])
          if y > 0:
               up = mp(x, y - 1)
          else:
               up = (-1, [])
          maxras = max(left[0], up[0]) + zed[x][y]
          if left[0] > up[0]:
               path = terra[x - 1, y][1].copy()
               path.append('D')
          else:
               path = terra[x, y - 1][1].copy()
               path.append('R')
          terra[x, y] = (maxras, path)
               return terra[x, y]
n, m = [int(i) for i in input().split()]
zed = [[int(i) for i in input().split()] for j in range(n)]
terra = {(0, 0): (zed[0][0], [])}
ans = mp(n - 1, m - 1)
print(ans[0])
print(' '.join(ans[1]))