Работа с двумерными массивами
Вложенные генераторы
Научимся использовать вложенные генераторы для заполнения двумерных массивов по формулам, которые зависят от номера строки и номера столбца элемента.
Мы уже встречались с генератором, который позволяет заполнить двумерный массив нулями:
a=[[0] * m for i inrange(n)]
Можно модифицировать этот генератор таким образом, чтобы внутренний список, состоящий из m нулей, тоже создавался через генератор:
a=[[0for j inrange(m)]for i inrange(n)]
Таким образом, мы получили два генератора, один из которых вложен в другой. Теперь, если в теле вложенного генератора вместо числа 0 записать какую-то формулу, зависящую от индексов i и j, то мы получим способ нетривиально заполнить наш двумерный массив. Ниже мы рассмотрим несколько примеров такого заполнения.
Пример 1
a = [[jfor j in range(m)]for i in range(n)]
Для n=3, m=4 этот генератор заполнит двумерный массив следующим образом:
0123
0123
0123
Пример 2
a=[[ifor j inrange(m)]for i inrange(n)]
Для n=3, m=4 этот генератор заполнит двумерный массив так:
0 0 0 0
1 1 1 1
2 2 2 2
Пример 3
a=[[i + j for j inrange(m)]for i inrange(n)]
Для n=3, m=4 этот генератор заполнит двумерный массив следующим образом:
0123
1234
2345
Пример 4
a=[[(int)(i== j)for j inrange(m)]for i inrange(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
4 10 20 35
Код на языке Python, решающий эту задачу, будет выглядеть следующим образом:
n, m =map(int,input().split())
w=[[1] * m for i inrange(n)]
for i inrange(1, n):
for j inrange(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 inrange(n)]
w=[[1] * m for i inrange(n)]
for i inrange(1, n):
w[i][0]= t[i][0] * w[i - 1][0]
for j inrange(1, m):
w[0][j]= t[0][j] * w[0][j - 1]
for i inrange(1, n):
for j inrange(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, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
