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

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

 

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

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

 

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

 

Задача 1.

 

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

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

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

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

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

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

 

 

 

 

 

 

Задача 2.

 

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

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

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

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

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

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

 

Задача 3.

 

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

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

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

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

 

Задача 4.

 

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

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

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

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

Задача 5.

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

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

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

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

 

 

Задача 6.

 

Квадранты

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

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

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

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

 

Рассмотрим следующую задачу. Дана прямоугольная доска из 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

2     

Код на языке 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])

Задача 7.

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

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

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

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

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

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

Задача 8.

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

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

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

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

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

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

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

 

Задача 9.

 

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

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

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

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

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

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

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

 

 

Задача 10

 

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

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

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

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

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

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

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