Подсчёт количества путей робота на сетке
Представьте себе робота, находящегося в левом верхнем углу сетки с координатами (X, Y). Робот может перемещаться в двух направлениях: вправо и вниз. Сколько существует маршрутов, проходящих от точки (0, 0) до точки (X, Y)?
Дополнительно:
Предположите, что на сетке существуют области, которые робот не может пересекать. Разработайте алгоритм построения маршрута от левого верхнего до правого нижнего угла.
Решение
Нам нужно подсчитать количество вариантов прохождения дистанции с Х шагов вправо и Y шагов вниз (X + Y шагов).
Чтобы создать путь, мы делаем Х шагов вправо так, чтобы общее количество перемещений оставалось фиксированным (X + Y). Таким образом, количество путей должно совпадать с количеством способов выбрать Х элементов из X + Y, то есть биномиальным коэффициентом. Биномиальный коэффициент из n по r имеет вид:
Для нашей задачи выражение будет следующим:
Даже если вы незнакомы с комбинаторикой, то все равно можете найти решение этой задачи самостоятельно.
Представим путь как строку длиной X + Y, состоящую из X символов R и Y символов D. Мы знаем, что из X + Y неповторяющихся символов мы можем составить (X + Y)! строк. Но в нашем случае используется X символов R и Y символов D. Символы R могут быть расставлены X! способами (то же самое мы можем сделать и с символами D). Таким образом, необходимо убрать лишние строки X! и Y!. В итоге мы получим то же самое выражение:
Дополнительно
Найдите маршрут (на карте есть места, через которые не может пройти робот).
Если мы изобразим нашу карту, то единственный способ попасть в квадрат (X, Y) — оказаться в одном из смежных квадратов: (X-1, Y) или (X, Y-1). Следовательно, необходимо найти путь к любому из этих квадратов ((X-1, Y) или (X, Y-1)).
Как это осуществить? Чтобы найти путь в квадрат (X-1, Y) или (X, Y-1), мы должны оказаться в одной из смежных ячеек. То есть нам необходимо найти путь к квадрату, смежному с (X-1, Y) ((X-2, Y) и (X-1, Y-1)) или (X, Y-1) ((X-1, Y-1) и (X, Y-2)). Обратите внимание: в наших рассуждениях точка (X-1, Y-1) упоминается дважды, мы еще вернемся к этому факту.
Давайте попробуем найти путь от исходного квадрата, двигаясь в обратном направлении, — начинаем с последней ячейки и пытаемся найти путь к каждому смежному квадрату. Далее приведен рекурсивный код, реализующий наш алгоритм.
public boolean getPath(int x, int y, ArrayList path) < Point p = new Point(x, y); path.add(p); if (x == 0 && y == 0) < return true; // найти путь >bolean success = false; if (x >= 1 && isFree(x – 1, y)) < // Пытаемся идти вправо success = getpath(x – 1, y, path); // Свободно! Можно идти вправо >if ( !success && y >= 1 && isFree(x, y - 1)) < // Пытаемся идти вниз success = getPath(x, y – 1, path); // Свободно! Можно идти вниз >if (!success) < path.remove(p); // Неверный путь! Прекратить движение этим маршрутом >return success; > Помните, что маршруты дублируются? Чтобы найти все пути к (X, Y), мы находим все пути к (X-1, Y) и (X, Y-1). Затем мы смотрим на координаты смежных квадратов: (X-2, Y), (X-1, Y-1), (X-1, Y-1) и (X, Y-2). Квадрат (X-1, Y-1) появляется дважды. Давайте будем запоминать посещенные квадраты, чтобы не тратить на них время.
Это можно сделать с помощью следующего алгоритма динамического программирования:
public Boolean getPath(int x, int y, ArrayList path, Hashtable cache) < Point p = new Point(x, y); if (cache.containsKey(p)) < // Мы уже посещали эту ячейку return cache.get(p); >path.add(p); if (x == 0 && y == 0) < return true; // Найден путь >boolean success = false; if (x >= 1 && isFree(X - 1, Y)) < //Пытаемся идти вправо success = getPath(x - 1, y, path, cache); // Свободно! Можно идти вправо >if (!success && y >= 1 && isFree(x, y - 1)) < // Пытаемся идти вниз success = getPath(x, y - 1, path, cache); // Свободно! Можно идти вниз >if (!success) < path.remove(p); //Неверный путь! Прекратить движение этим маршрутом >cache.put(p, success); // Вычисляем результат return success; > Это простое изменение сделает наш код более быстрым.
Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»
Е18.18 Определите количество способов, которыми Робот может попасть из левой верхней клетки в правую нижнюю.
Исходные данные для Робота записаны в файле в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.
(количество способов)
«Некрыловские варианты» от Евгения Джобса — Вариант 5
Решение:
Ответ: 33480
Рубрика «ЕГЭ Задание 18»
ЕГЭ информатика 18 задание разбор, теория, как решать.
Динамическое программирование в электронных таблицах. Робот-сборщик монет, (П) — 1 балл
Е18.21 В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя.
31.12.2023 ЕГЭ Задание 18 Администратор Комментарии: 0
Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа. За один ход робот может переместиться на одну клетку вправо или на одну клетку …
Е18.20 Определите минимальный начальный запас энергии
18.12.2023 ЕГЭ Задание 18 Администратор Комментарии: 0
Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Некоторые клетки выделены тёмным фоном. В эти клетки роботу заходить нельзя. Клетка, из которой робот не может сделать допустимого хода (справа и сверху находятся …
учебники по паскалю / Для начинающих от Долинского / Ochered / Ochered
О
лимпиадные задачи на очередь 7 апреля 2006
8. Минное поле 14
9. Индиана Джонс 17
13. Настольная игра 25
14. Интересная игра 26
2. Лабиринт 1 32
3. Лабиринт 2 34
4. Лабиринт 3 36
5. Летит утка 39
8. Минное поле 48
9. Индиана Джонс 50
12a. Игра 2 (первое решение) 57
12b. Игра 2 (второе решение) 60
13. Настольная игра 63
14. Интересная игра 66
Очередь\Олимпиадные задачи\1. Паук Баллов 20
Ученые открыли новую разновидность паука, который плетет паутину не как все пауки, а по-своему и передвигается по ней определенными шагами. Паутина имеет вид квадрата, в которой 9 столбцов и 9 строк. Определить сколько шагов понадобится пауку, чтобы добраться из одной клетки паутины в другую, если известно как он по ней передвигается.(см.ниже)
0 — клетка в которой находится паук 1 — клетки в которые может пойти паук 2 — клетка в которую должен попасть паук
Формат ввода:
Х Y — координаты точки, в которой находится паук
X1 Y1 — координаты точки, в которую должен попасть паук
Формат вывода:
K — наименьшее число шагов, которое пауку понадобится, чтобы дойти из одной клетки своей паутины в другую.
Пример ввода:
Пример вывода:
Решение на стр. 30
Компилятор: Отправка решения:
Очередь\Олимпиадные задачи\2. Лабиринт 1 Баллов 30
Есть лабиринт. Он представляет собой прямоугольник N (строк) на M (столбцов). Мальчик находится в клетке с координатами (X; Y) (X — столбец, Y — строка). Сможет ли он пробраться в клетку (X1; Y1) (X1 — столбец, Y1 — строка), если мальчик может двигаться по горизонтали или по вертикали. Начало координат, клетка (1; 1), находится в первой строке и в первом столбце.
Мальчик всегда появляется на свободной клетке.
В лабиринте:1- стена.0- проход.
Формат ввода:
N M — размер лабиринта.
X Y — координаты начального положения мальчика.
X1 Y1 — координаты клетки в которую мальчику необходимо попасть.
Далее следует N строк — описание лабиринта.
Фортмат вывода:
Yes/No — ‘Yes’ в случае когда мальчик сможет добраться до нужной клетки и ‘No’ в противном случае.
Пример ввода:
Пример вывода:
Решение на стр. 32
Компилятор: Отправка решения:
Очередь\Олимпиадные задачи\3. Лабиринт 2 Баллов 30
Дан лабиринт NxM. 0-проход. 1-стена. Начальная точка 1 1, Конечная точка n m. За 1 ход можно пойти в одну из 8 соседних клеток (см. рис.1).Можно ли дойти из начальной точки в конечную?
Рис.1
Формат ввода:
Формат вывода:
Пример ввода:
Пример вывода:
Решение на стр. 34
Компилятор: Отправка решения:
Очередь\Олимпиадные задачи\4. Лабиринт 3 Вераксич Сергей и Миняйлов Вова Баллов 30
Человек попал в лабиринт. С собой у него были: карта и k метров веревки. На карте цифрой 1 обозначена стена, а любой другой цифрой обозначен проход. Чтобы пройти комнату человек должен тратить метр веревки. Если он сможет выйти, то вывести yes и минимальное количество метров веревки, которое ему понадобится. Если выхода нет вывести no. А если выход есть, но не хватает веревки, то вывести no и количество не хвативших метров. Выход это любая цифра кроме 1 на краю лабиринта.
Примечание: На начальную комнату веревка не тратится.
Формат ввода:
Формат вывода:
Пример ввода:
Пример вывода:
Решение на стр. 36
Компилятор: Отправка решения:
Очередь\Олимпиадные задачи\5. Летит утка Миняйлов Вова и Громыко Саша Баллов 30
Наступает зима. Утки улетают на юг. Для того, что бы попасть на юг им надо пересечь море. Море представлено матрицей A. Если элемент (i,j) этой матрицы равен 0, то это вода и утка может там пролететь, а если он равен 1, то там скала, и утка не может там лететь. Утка может двигаться только в клетки, имеющие с ее текущей клеткой общую сторону. На переход между клетками она тратит одну единицу энергии. Изначально у нее t единиц энергии. Вам нужно вывести сможет ли она долететь из точки xn;yn в точку xk;yk. Если сможет, вывести минимальное число единиц энергии, которое она затратит на перелет.
Формат ввода:
N M T — размер и количество энергии.
Формат вывода:
Пример ввода:
Пример вывода:
Решение на стр. 39
Компилятор: Отправка решения:
Очередь\Олимпиадные задачи\6. Игра 1 Вераксич Сергей и Миняйлов Владимир Баллов 30
Известный хакер «MVienriaakisliocvh» играл в игру. Он не может ее пройти, и обращается к вам за помощью. Игра проводится по следующим правилам:
1. Играют на поле размером NxM.
2. Ходить можно только по смежным клеткам.
3. Задача добраться от начальной точки(x1,y1) до конечной(x2,y2).
4. У каждой клетки есть свое содержание.
5. Содержания, в которые можно ходить следующие: 24680eyuioajEYUIOAJуеыаояиюУЕЫАОЭэЯИЮ
Вам надо вывести можно или нельзя добраться из начальной в конечную. Если можно, то вывести минимальное число ходов.
Формат ввода:
Формат вывода:
Yes минимальное кол-во ходов
Пример ввода:
Пример вывода:
Решение на стр. 42
Компилятор: Отправка решения:
Очередь\Олимпиадные задачи\7. Мальчик Вераксич Сергей и Шлягровский Владимир Баллов 25
Один мальчик очень любит играть в игры с числами. Он берёт тетрадь и пишет числа в таблице N*M. Он стоит в клетке (1,1) и хочет попасть в клетку (N,M). Ходить можно только по чётным цифрам на одну клетку по вертикали или горизонтали. Если он дойдёт до конца вывести Yes и за сколько минимально ходов дойдёт или No, если не дойдёт.
Формат ввода:
A — число в таблице
Xod — за сколько минимально ходов дойдёт
Формат вывода:
Пример ввода:
Пример вывода:
Решение на стр. 45
Компилятор: Отправка решения:
Очередь\Олимпиадные задачи\8. Минное поле Баллов 24
Формат ввода:
L — длина минного поля
M — ширина минного поля
x1 y1 — координаты приземления парашютиста относительно минного поля (0 x2 y2 — координаты точки, в которую ему нужно попасть (0 N — количество мин на поле (0<=N<=20) x[n] y[n] — где (x[i],y[i]) — координаты i-той мины (0 Формат вывода: «Yes», если существует такой путь, «No», если такого пути не существует. Пример ввода: Пример вывода: Решение на стр. 48 Компилятор: Отправка решения: Очередь\Олимпиадные задачи\9. Индиана Джонс Миняйлов Владимир и Вераксич Сергей Баллов 30 Индиана Джонс нашел карту лабиринта (размером N*M). Лабиринт заполнен различными монстрами. У Индианы Джонса есть биологическое оружие, которое может убить K видов монстров. Индиана Джонс находится в точке (X1 Y1), а выход в точке (X2 Y2). Сможет ли Джонс выйти из лабиринта. Чтобы перейти из комнаты(1) в другую комнату(2) нужно уничтожить монстра в комнате(2). На клетки, в которых Джонс уже был идти нельзя т.к. он их заминировал. Ходить можно только по вертикали и горизонтали на одну клетку. В точке (X1 Y1) монстры безобидные. Нужно узнать сможет или нет Джонс выйти, и, если сможет, то узнать какое минимальное количество ходов которое он сделает, прежде чем выйдет. Монстры могут обозначаться любым одним символом. Формат ввода: L — Виды монстров, которых может уничтожить биологическое оружие Индианы Джонса. Формат вывода: No/Yes Kol — минимальное количество ходов, которое сделает Индиана Джонс,прежде чем выйдет. Пример ввода: Пример вывода: Решение на стр. 50 Компилятор: Отправка решения: Очередь\Олимпиадные задачи\10. Поле Баллов 30 В один день коровы захотели поделить поле(N*M) на K кусков. Путем удаления C кусков, после чего поле распадётся на K кусков. Помогите узнать K. Формат ввода: X[1] Y[1], X[2] Y[2] . . . X[C],Y[C] X Y — Координаты клеточек которые нужно удалить. M — не больше 150 N — не больше 150 C — количество границ (не больше 1000) Формат вывода: K- количество кусков. Пример ввода: Пример вывода: Решение на стр. 53 Компилятор: Отправка решения: Очередь\Олимпиадные задачи\11. Праздник Миняйлов Владимир и Вераксич Сергей Баллов 30 Формат ввода: Формат вывода: Nom[1] Nom[2] . Nom[K] Пример ввода: Пример вывода: Решение на стр. 55 Компилятор: Отправка решения: Очередь\Олимпиадные задачи\12. Игра 2 Миняйлов Вова и Громыко Саша Баллов 30 На доске размером NxM ведется игра. В каждой клеточке поля либо стена либо штраф, заданный некоторым числом. Вам надо дойти из клетки (xn,yn) в клетку (xk,yk). Можно ходить только в смежные клетки, то есть клетки, имеющие общую сторону. Нельзя заходить в клетку со стеной. Вам нужно найти путь из начальной клетки в конечную по вышеуказанным правилам так, чтобы суммарный штраф, собранный по пути, был минимален. Примечание 1: штраф начальной клетки входит в суммарный штраф, суммарный штраф Примечание 2: стена обозначается как -1. Формат ввода: xn yx — координаты начальной клетки xk yk — координаты конечной клетки a[2,1] a[2,2] . a[2,m] — поле Формат вывода: Yes st — если можно дойти (st — минимальный штраф). No — если дойти нельзя. Пример ввода: Пример вывода: Решение на стр. 57 (первое) Решение на стр. 60 (второе) Компилятор: Отправка решения: Очередь\Олимпиадные задачи\13. Настольная Игра Баллов 20 Раньше были популярны настольные игры с кубиком. Игра заключалась в следующем: Играют несколько человек. Игровое поле поделено на клетки. Каждый игрок, по очереди, бросает кубик и движется вперед на столько клеток, сколько выпадет на кубике. Также есть призовые и штрафные клетки, например ‘перейти на 10 клеток вперед’, ‘пропустить ход’ и т.д. Ваша задача определить сколько минимально раз нужно бросить кубик одному игроку, чтобы прийти к финишу, при условии что кубик будет выдавать наилучшие числа. Финишем является последняя клетка доски. Вначале игрок стоит перед первой клеткой. Выход за пределы игрового поля — проигрыш. На кубике могут выпадать числа 1, 2, 3, 4, 5, и 6. Формат ввода: N — размер доски. (N A1 A2 A3 . An — числа, характеризующие клетки доски: Ai = 0 — обыкновенная клетка; Ai = 100 призовой ход (т.е. игрок снова бросает кубик и двигается вперед, призовой ход не учитывается в общем числе бросаний кубика); Ai = -100 пропуск хода (т.е. игрок бросает кубик, но не переставляет фишку); Все остальные значения Ai показывают на какое число клеток необходимо перейти вперед (если число отрицательное, то игрок должен двигаться назад) не бросая кубик (т.е. если фишка попала на такую клетку то она автоматически переносится вперед или назад на указанное в Ai кол-во клеток); Формат вывода: Минимальное число бросаний кубика, чтобы прийти к финишу. Пример ввода: 0 0 0 0 5 0 0 0 0 0 Пример вывода: Примечание: В данном примере необходимо чтобы игрок бросил кубик и выпало число 5, тогда он должен пройти еще на 5 шагов вперед, не бросая кубик, и окажется на финише. Решение на стр. 63 Компилятор: Отправка решения: Очередь\Олимпиадные задачи\14. Интересная игра Зайцев Иван Баллов 25 Рассмотрим следующую игру: Имеется доска, разделенная на клетки. В каждой клетке стоит некоторое число. Из одной клетки можно перейти в другую, если расстояние между этими клетками равно числу в той клетке, куда делается ход. Игрок начинает ходить из клетки (X1,Y1). Определить за какое минимальное количество ходов игрок может переместиться в клетку (X2,Y2). Расстояние между клетками (A,B) и (C,D) вычисляется по формуле: abs(C-A)+abs(D-B) (здесь abs — это модуль числа, т.е. abs(-5)=5, abs(7)=7, abs(0)=0). Формат ввода: N M — размер доски по вертикали и горизонтали. A21 A22 . A2m — числа в соответствующих клетках доски. Формат вывода: L — минимальное количество ходов.
