Сообщение Re: Красная Шапочка и Серый Волк от 11.11.2016 12:54
Изменено 11.11.2016 13:15 antonio_v_krasnom
Здравствуйте, olimp_20, Вы писали:
Опишу, как я ее решил.
Моё решение скорей всего чем-то похоже на приведенные выше.
На первом шаге есть начальная координата красной шапочки (далее КШ) и она может посетить некоторые соседние клетки. Заполняем множество (std::set) клеток, куда она может пойти.
На каждом следующем шаге перебираем множество клеток предыдущего шага и строим новое множество клеток, куда она может пойти из каждой из них. При этих переходах учитывается позиция волка (начальная и конечная — для 2 соседних шагов) — клетка с волком занята.
Каждый новый шаг — каждое новое множество клеток.
Как только среди этих клеток появится клетка бабушки — финиш.
Поскольку в условии сказано, что КШ гарантированно придет к бабушке, отслеживать бесконечное блуждание не надо (если б надо было — как вариант еще можно хранить карту слепков текущего множества клеток — то есть на каждом шаге из множества клеток строим некоторый слепок/хэш и помещаем его в отдельную карту, заполнять эту карту начинаем только после остановки волка).
Попробуем оценить время.
Вначале кол-во клеток будет расти квадратично от кол-ва шагов, далее довольно быстро оно насытится и будет примерно постоянным, не больше N*M.
Время расчета перехода на следующую клетку это О(1) для каждой клетки, т.е. для всех клеток на каждом шаге — О(N*M).
Если кол-во ходов обозначить за Х, то полное время О(N*M*Х).
150*150*32000 = 720.000.000
Можно на сильном железе вытянуть за секунду столько?
Например, бабушка будет жить среди плотной застройки деревьев, и волк её будет 31999 ходов охранять, не давая пройти.
Если нельзя — будем оптимизировать. ))
| Скрытый текст | |
| _>Лимит времени 1с. _>Красная Шапочка спешит навестить свою больную бабушку и отнести ей лекарства и еду. Ее путь лежит через густой лес, который разбит на квадраты. С квадрата в квадрат можно попасть только двигаясь вверх, вниз, влево или вправо. За пределы леса выходить нельзя, лес окружен непроходимым болотом. Лес имеет форму прямоугольника в котором N строк и M столбцов. Красная Шапочка живет в левом верхнем углу этого леса, а ее бабушка — в правом нижнем. Дом бабушки охраняют охотники. Тем лесом бродит Серый Волк, которого очень надо остерегаться Красной Шапочке. К счастью, исходное положение и маршрут его ей известны. _>За какую наименьшее количество шагов Красная Шапочка может достичь своей цели, соблюдая при движении такие правила (шаг — это перемещение из клетки в соседнюю клетку): _>1. Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку. _>2. Перемещение осуществляется поочередно: сначала Серый Волк, потом Красная Шапочка. _>3. Не допускается нахождение в одном квадрате Красной шапочки и Серого Волка. _>4. Ходы Красной шапочки и Серого Волка обязательны. _>5. Если ходы Серого Волка закончились, то он остается в последней достигнутой клетке. Но заранее известно, что он при этом не заблокирует путь Красной Шапочки к бабушке. Если Серый Волк достиг финиша (квадрата в котором живет бабушка), то его убивают охотники. _>Входные данные _>В первой строке размер поля: два числа через пробел 0<N, M≤150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) — Клетка свободна. Решетка (#) — непроходимая клетка. В следующей строке два числа — номер строки и столбца, где изначально находится Серый Волк. Далее идет строка с описанием пути Серого Волка: R — движение вправо, L — влево, U — вверх, D — вниз. Количество ходов соперника не более 32000. _>Исходные данные _>Единственное число — минимальное число шагов, необходимое для достижения финиша. _> _>Как мене представляется — тут можно использовать волновой алгоритм (обход в ширину) Правда возникает тревожное ощущение, что условию задачи может соответствовать ситуация: КШ видит, что столкнется с СВ, отступает на несколько шагов, пропуская волка, а потом двигается дальше. Действительно ли КШ может быть такой интеллектуальной в этой задаче? Если да, то в чем состоит модификация волнового алгоритма? Или тут нужен совсем другой подход? Выполнение программы — 1с. | |
Опишу, как я ее решил.
Моё решение скорей всего чем-то похоже на приведенные выше.
На первом шаге есть начальная координата красной шапочки (далее КШ) и она может посетить некоторые соседние клетки. Заполняем множество (std::set) клеток, куда она может пойти.
На каждом следующем шаге перебираем множество клеток предыдущего шага и строим новое множество клеток, куда она может пойти из каждой из них. При этих переходах учитывается позиция волка (начальная и конечная — для 2 соседних шагов) — клетка с волком занята.
Каждый новый шаг — каждое новое множество клеток.
Как только среди этих клеток появится клетка бабушки — финиш.
Поскольку в условии сказано, что КШ гарантированно придет к бабушке, отслеживать бесконечное блуждание не надо (если б надо было — как вариант еще можно хранить карту слепков текущего множества клеток — то есть на каждом шаге из множества клеток строим некоторый слепок/хэш и помещаем его в отдельную карту, заполнять эту карту начинаем только после остановки волка).
Попробуем оценить время.
Вначале кол-во клеток будет расти квадратично от кол-ва шагов, далее довольно быстро оно насытится и будет примерно постоянным, не больше N*M.
Время расчета перехода на следующую клетку это О(1) для каждой клетки, т.е. для всех клеток на каждом шаге — О(N*M).
Если кол-во ходов обозначить за Х, то полное время О(N*M*Х).
150*150*32000 = 720.000.000
Можно на сильном железе вытянуть за секунду столько?
Например, бабушка будет жить среди плотной застройки деревьев, и волк её будет 31999 ходов охранять, не давая пройти.
Если нельзя — будем оптимизировать. ))
Re: Красная Шапочка и Серый Волк
Здравствуйте, olimp_20, Вы писали:
Опишу, как я ее решил.
Моё решение скорей всего чем-то похоже на приведенные выше.
На первом шаге есть начальная координата красной шапочки (далее КШ) и она может посетить некоторые соседние клетки. Заполняем множество (хэш-таблица или битовый массив) клеток, куда она может пойти.
На каждом следующем шаге перебираем множество клеток предыдущего шага и строим новое множество клеток, куда она может пойти из каждой из них. При этих переходах учитывается позиция волка (начальная и конечная — для 2 соседних шагов) — клетка с волком занята.
Каждый новый шаг — каждое новое множество клеток.
Как только среди этих клеток появится клетка бабушки — финиш.
Поскольку в условии сказано, что КШ гарантированно придет к бабушке, отслеживать бесконечное блуждание не надо (если б надо было — как вариант еще можно хранить карту слепков текущего множества клеток — то есть на каждом шаге из множества клеток строим некоторый слепок/хэш и помещаем его в отдельную карту, заполнять эту карту начинаем только после остановки волка).
Попробуем оценить время.
Вначале кол-во клеток будет расти квадратично от кол-ва шагов, далее довольно быстро оно насытится и будет примерно постоянным, не больше N*M.
Время расчета перехода на следующую клетку это О(1) для каждой клетки, т.е. для всех клеток на каждом шаге — О(N*M).
Если кол-во ходов обозначить за Х, то полное время О(N*M*Х).
150*150*32000 = 720.000.000
Можно на сильном железе вытянуть за секунду столько?
Например, бабушка будет жить среди плотной застройки деревьев, и волк её будет 31999 ходов охранять, не давая пройти.
Если нельзя — будем оптимизировать. ))
| Скрытый текст | |
| _>Лимит времени 1с. _>Красная Шапочка спешит навестить свою больную бабушку и отнести ей лекарства и еду. Ее путь лежит через густой лес, который разбит на квадраты. С квадрата в квадрат можно попасть только двигаясь вверх, вниз, влево или вправо. За пределы леса выходить нельзя, лес окружен непроходимым болотом. Лес имеет форму прямоугольника в котором N строк и M столбцов. Красная Шапочка живет в левом верхнем углу этого леса, а ее бабушка — в правом нижнем. Дом бабушки охраняют охотники. Тем лесом бродит Серый Волк, которого очень надо остерегаться Красной Шапочке. К счастью, исходное положение и маршрут его ей известны. _>За какую наименьшее количество шагов Красная Шапочка может достичь своей цели, соблюдая при движении такие правила (шаг — это перемещение из клетки в соседнюю клетку): _>1. Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку. _>2. Перемещение осуществляется поочередно: сначала Серый Волк, потом Красная Шапочка. _>3. Не допускается нахождение в одном квадрате Красной шапочки и Серого Волка. _>4. Ходы Красной шапочки и Серого Волка обязательны. _>5. Если ходы Серого Волка закончились, то он остается в последней достигнутой клетке. Но заранее известно, что он при этом не заблокирует путь Красной Шапочки к бабушке. Если Серый Волк достиг финиша (квадрата в котором живет бабушка), то его убивают охотники. _>Входные данные _>В первой строке размер поля: два числа через пробел 0<N, M≤150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) — Клетка свободна. Решетка (#) — непроходимая клетка. В следующей строке два числа — номер строки и столбца, где изначально находится Серый Волк. Далее идет строка с описанием пути Серого Волка: R — движение вправо, L — влево, U — вверх, D — вниз. Количество ходов соперника не более 32000. _>Исходные данные _>Единственное число — минимальное число шагов, необходимое для достижения финиша. _> _>Как мене представляется — тут можно использовать волновой алгоритм (обход в ширину) Правда возникает тревожное ощущение, что условию задачи может соответствовать ситуация: КШ видит, что столкнется с СВ, отступает на несколько шагов, пропуская волка, а потом двигается дальше. Действительно ли КШ может быть такой интеллектуальной в этой задаче? Если да, то в чем состоит модификация волнового алгоритма? Или тут нужен совсем другой подход? Выполнение программы — 1с. | |
Опишу, как я ее решил.
Моё решение скорей всего чем-то похоже на приведенные выше.
На первом шаге есть начальная координата красной шапочки (далее КШ) и она может посетить некоторые соседние клетки. Заполняем множество (хэш-таблица или битовый массив) клеток, куда она может пойти.
На каждом следующем шаге перебираем множество клеток предыдущего шага и строим новое множество клеток, куда она может пойти из каждой из них. При этих переходах учитывается позиция волка (начальная и конечная — для 2 соседних шагов) — клетка с волком занята.
Каждый новый шаг — каждое новое множество клеток.
Как только среди этих клеток появится клетка бабушки — финиш.
Поскольку в условии сказано, что КШ гарантированно придет к бабушке, отслеживать бесконечное блуждание не надо (если б надо было — как вариант еще можно хранить карту слепков текущего множества клеток — то есть на каждом шаге из множества клеток строим некоторый слепок/хэш и помещаем его в отдельную карту, заполнять эту карту начинаем только после остановки волка).
Попробуем оценить время.
Вначале кол-во клеток будет расти квадратично от кол-ва шагов, далее довольно быстро оно насытится и будет примерно постоянным, не больше N*M.
Время расчета перехода на следующую клетку это О(1) для каждой клетки, т.е. для всех клеток на каждом шаге — О(N*M).
Если кол-во ходов обозначить за Х, то полное время О(N*M*Х).
150*150*32000 = 720.000.000
Можно на сильном железе вытянуть за секунду столько?
Например, бабушка будет жить среди плотной застройки деревьев, и волк её будет 31999 ходов охранять, не давая пройти.
Если нельзя — будем оптимизировать. ))