1. Зарегистрируйтесь на сайте repl.it;
2. Перейдите в раздел my repls;
3. Нажмите кнопку Start coding now! - если вы приступаете впервые, или New Repl - если у вас уже есть работы;
4. В списке языков выберите тот язык, который изучаете;
5. Код пишите в левой части окна - в редакторе кода;
6. Чтобы посмотреть результат выполнения файла, нажмите на кнопку Run. Результат появится в правой части окна;
7. После окончания работы скопируйте ссылку на ваш repl в адресной строке браузера;
8. Скопированную ссылку (ваше решение ДЗ) нужно отправить на проверку. Для этого перейдите в личный кабинет на сайте netology.ru, в поле комментария к домашней работе вставьте скопированную ссылку и отправьте работу на проверку;
У вас есть квадратное поле клеток n на n. В каждой клетке может находиться кактус. В левом верхнем углу находится щенок. Щенок может перемещаться только на клетку вправо или на клетку вниз, причём он не может премещаться в клетку, в которой находится кактус.
Вам надо написать функцию, которая принимала бы параметрами поле в виде двумерного массива, две координаты клетки, в которой находится хозяин щенка, и которая выводила бы на экран поле с маршрутом для щенка из левого верхнего угла до человека. Если такого маршрута нет, программа должна сообщить об этом.
Координаты считаются так: слева сверху x = 0, y = 0, координата x растёт вправо, координата y растёт вниз, т.е. левый нижний угол имеет координаты (0; n-1), правый нижний (n-1; n-1), правый верхний (n-1; 0).
Например, поле может выглядеть так (Щ - щенок, Ч - человек, * - кактус):
Щ - - * * - - - - -
- - - - * - * * - -
- - - * - * - - - *
- * - - - - - - Ч -
- - - - - - * - - -
- - * - - * - - - -
- - - * - - * * * -
- - - - - - - * - -
- - - - - - - * - -
- - - - - * * - - -
Результат работы программы (x - маршрут щенка):
Щ - - * * - - - - -
x - - - * - * * - -
x x x * - * - - - *
- * x x x x x x Ч -
- - - - - - * - - -
- - * - - * - - - -
- - - * - - * * * -
- - - - - - - * - -
- - - - - - - * - -
- - - - - * * - - -
Программа должна работать за время и дополнительную память не хуже чем O(n2). Подумайте, как бы вы решили задачу, используя принцип динамического программирования?
Давайте решим вспомогательную задачу и напишем функцию, которая вместо прорисовки готового поля будет просто возвращать для полученных в параметрах координат направление, откуда в эту клетку прибежит щенок если такой путь существует: U если щенок в эту клетку прибежит сверху, L если слева, N если щенок не может добраться в эту клетку. Если может прибежать с обоих направлений, то выбираем любое из них.
Пусть мы уже написали такую функцию и назвали её where_from(field, x, y). Теперь решим нашу исходную задачу через эту вспомогательную: просто вызовем от запрашиваемых координат вспомогательную задачу, она даст нам направление, откуда прибежит щенок. Перейдём по этому направлению и вызовем вспомогательную задачу уже от новых координат. Будем так делать до тех пор, пока не дойдём до клетки с координатами (0; 0), т.е. до изначальной клетки для щенка:
find_path(field, x0, y0):
path = [n x n значений "нет"]
memory = двумерный массив заполненный "?"
x = x0
y = y0
while (x; y) это не (0; 0)
direction = where_from(field, x, y)
if direction == 'N'
return Нет такого пути :(
else if direction == 'U'
path[x][y] = "да"
y -= 1
else if direction == 'L'
path[x][y] = "да"
x -= 1
for y от 0 до n
for x от 0 до n
if x == x0 и y == y0
печатаем 'Ч'
else if path[x][y]
печатаем 'x'
else
печатаем field[x][y]
Как же теперь быстро и эффективно решить вспомогательную задачу, т.е. написать функцию where_from? Давайте решим её динамикой! А именно, решение для заданных координат будем выражать через рекурсивное решение для других координат, а все ответы будем запоминать в двумерном массиве чтобы не пересчитывать.
Как же нам написать рекурсивное решение? Давайте подумаем, если мы находимся в клетке с координатами (x; y), то в качестве ответа от нас ждут U если щенок может прибежать в неё сверху, L если слева, N если не может сюда прибежать (если может с обоих направлений, то указать любое из них). Рекурсия будет выглядить следующим образом: если слева у нас доступная клетка, не кактус, то вызовем рекурсивно where_from от неё и, если этот вызов вернул не N (т.е. в эту клетку может попасть щенок), то и мы вернём в качестве ответа L (т.е. иди из текущей в левую). Если же нам вернули N, то провернём тоже самое с верхней клеткой. Если же и у неё N (или там были кактусы, или клеток не было тк мы были на границе поля), то вернём N.
Не забудем запоминать для каждой вызванной координаты ответ в двумерном массиве, который будем передавать дополнительным параметром. Рекурсия гарантировано закончится, тк на каждом вызове мы двигаемся либо влево, либо вверх, а такое делать бесконечно невозможно. Запоминание результатов в массиве гарантирует нам, что для каждой клетки максимум только один раз произойдут рекурсивные вызовы. В результате, мы получим суммарную асимптотику O(n2), тк количество ячеек n2.
where_from(field, x, y, memory):
if memory[x][y] != '?'
return memory[x][y]
if x > 0
left_x = x - 1
left_y = y
if left_x == 0 И left_y == 0
memory[x][y] = 'L'
return 'L'
if field[left_x][left_y] != '*'
if where_from(field, left_x, left_y, memory) != 'N'
memory[x][y] = 'L'
return 'L'
if y > 0
up_x = x
up_y = y - 1
if up_x == 0 И up_y == 0
memory[x][y] = 'U'
return 'U'
if field[up_x][up_y] != '*'
if where_from(field, up_x, up_y, memory) != 'N'
memory[x][y] = 'U'
return 'U'
memory[x][y] = 'N'
return 'N'
- В начале работы программы заведите
nравную10и двумерный массив для поля, заполните его как в примере выше (клеткуЧзаменить на-). - Напишите функции
find_pathиwhere_from. Не забудьте адаптировать код первого метода так, чтобы передавать вwhere_fromмассив для памяти динамического программированияmemory. - Вызовите
find_pathдля координаты (8; 3). Убедитесь, что построился верный путь для щенка. - Загрузите ваше решение на сайт repl.it, отправьте ссылку на него на проверку.