Это последний спринт ... и половина вашей команды заболела. Вы работаете поздно, просто делаете свой последний коммит в течение дня, с нетерпением ожидая ... почему выключили свет? Я не помню, чтобы охранник приходил ... о, нет! Я оставил свои ключи дома!

По мере того, как весь ужас ситуации погружается, вы решаете, что вы собираетесь сбежать .

Резюме задачи

Чтобы осуществить побег, вам нужен план! Однако вы знаете, что любой план может потерпеть неудачу, и разные планы требуют разных усилий.

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

Вы делаете карту здания:

#######################
#                =    #
!                =    !    <-- window
#          !     =    #        (freedom!)
#################=    #
#    #           =    #
#    #           =    #
#    #           =    #
# o  !   # #  !  =    #
##|  !  ## #  !  =    #
#######################

  ^  ^           ^
  me my door     ludicrously high shelves
     (locked)    (climbable)

Чтобы сбежать из офиса, вам придется убраться с карты. Здесь вы видите 2 окна ( !), каждое из которых приведет вас к свободе, но доступно только одно из них. Мы определяем «вне карты» как то, что ваши ноги находятся за пределами карты

Типы клеток

  - empty, you can be here (i.e. the escapee can consume this cell)
# - solid (your desk, your in-tray), you can't be here, but you can stand on it
! - destructible, (co-worker's desk, door, window), you can't be here until you smash it first (turning it into an empty cell)
= - climbable, (fire ladder, filing cabinet, etc.), you can be here

Клетки, первоначально использованные беглецом, считаются пустыми.

Технические характеристики действий

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

шаг

1 ст, 100%, зеркало

 o.            o
 |.   -->      |
 #            #

Точки показывают ячейки, которые должны быть пустыми (или проходимыми, но не сплошными или разрушаемыми), потому что мы движемся в него или через него. 100% означает, что у вас есть 100% шанс не навредить себе и закончить свой дерзкий побег. Все вероятности будут целочисленными процентами между 1% и 100% включительно. Первая диаграмма показывает начальное состояние (стоя на чем-то твердом, стоя рядом с каким-то пустым пространством). Вторая диаграмма показывает состояние терминала (перенесено в пустое пространство). Нет никаких требований для каких-либо неуказанных ячеек (пробелов, ) слева (начальное состояние) быть чем-то конкретным. Неуказанные клетки (пробел,) справа (состояние терминала) должно быть таким же, каким они были до этого (например, за тем, что было за беглецом, или за тем, на что я хожу (будь то пустое пространство или иным образом). Обратите внимание, что все справа (состояние терминала) ) диаграммы изменят только ячейки с разрушаемых на пустые, никаких других изменений не произойдет. «1 stp» означает, что это стоит 1 stp: мы определяем «stp» как количество энергии, необходимое для выполнения шага.

«зеркало» означает, что это действие имеет две формы. «Правое» действие показано, «левое» действие является точным зеркалом, например:

.o
.|
 # 

это зеркальная (левая) форма

o.
|.
# 

Правое действие называется «Right» (например, «Step Right»). Левое действие называется «Left» (например, «Step Left»).

На этих диаграммах беглец показан

o
|

в положении стоя (2 шт.) и

%

когда приседает (1 единица в высоту). Клетки , которые должны быть твердыми или разрушаемые обозначены хэш, #. Клетки, которые не должны быть твердыми или разрушаемыми, обозначены точкой .. Клетки, которые должны быть разрушаемыми, обозначены ударом !. Вновь созданное пустое пространство показано подчеркиванием _. xявляется контрольной точкой, которая не перемещается (она не существует, нет ограничений на то, какой должна быть эта ячейка (например, пробел )).

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

шаг

1 ст, 100%, зеркало

 o.         o
 |.  -->    |
x#        x#

Подняться

1 ст, 100%, зеркало

 =         =
 o.  -->    o
 |.         |
x=        x= 

шарканье

3 ст, 100%, зеркало

 %.         %
x#   -->  x# 

Карабкаться вверх

10 шт, 95%, зеркало

 o.         %
 |#  -->    #
x#        x#

Капля

0 стп, 100%

 o         
 |  -->   o
x.       x|

Drop (Стенд)

0 стп, 100%

 %        o
x.  -->  x|

Подняться

2 ст, 100%

 =        o
 o  -->   |
x|       x

пресмыкаться

2 ст, 100%

 o
 |  -->   %
x#       x#

стенд

4 ст, 100%

 .        o
 %  -->   |
x#       x#

Прыжок в длину

4 ст, 95%, зеркало

 o..          o
 |..  -->     |
x#         x#

Длинный прыжок

7 шт, 75%, зеркало

 o...           o
 |...  -->      |
x#          x#

Высокий прыжок

12 шт, 90%, зеркало

 ..         o
 o.  -->    |
 |          
x#        x# 

Положи свою спину в это!

20 шт, 80%, зеркало

 o!.         _o
 |!.  -->    _|
x#         x#

перфоратор

8 шт, 90%, зеркало

 o!        o_
 |   -->   |
x#        x#

Удар

8 шт, 85%, зеркало

 o         o
 |!  -->   |_
x#        x#

Печать

8 ст, 90%

 o        o
 |  -->   |
x!       x_

планы

План - это последовательность действий, определенных выше. Например:

Step Left
High Jump Left
Crouch
Shuffle Left
Shuffle Left
Stand
Long Jump Left
Put your back into it! Left
Step Left

Обратите внимание на включение капель. Правила должны быть установлены так, чтобы вы не делали ничего, кроме бросания, но вы все равно должны планировать это!

Любой план требует усилий, которые являются суммой усилий для каждого шага. Существует также вероятность успеха, которая является продуктом вероятности успеха каждого действия. Простой пример:

Step Right:          1stp,  100%
Long Jump Right:     7stp,  75%
Step Right:          1stp,  100%
Stamp:               8stp,  90%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Step Left:           1stp,  100%
Step Left:           1stp,  100%
High Jump Left:      12stp, 90%

Effort = 1+7+1+8+1+1+12 = 31
Success Probability = 75%*90*90% = 60.75%

«Рабочий пример» для карты в верхней части страницы можно найти как суть .

вход

Входные данные состоят из двух частей: целого числа и массива или строки символов.

Целое число - это минимально допустимая (процентная) вероятность успеха. Его следует интерпретировать как процент, поэтому 80 означает, что ваш план должен быть успешным с вероятностью не менее 80%.

Действительная карта - это прямоугольник, который включает стоящего беглеца (минимальный размер 1x2) и не содержит никаких неопределенных символов. Все строки будут одинаковой длины. Вы можете принять входные данные как одномерную строку с разделителями (разделитель должен быть одним непротиворечивым символом или одним из пары CRLF и LFCR), как аналогичный одномерный массив или двумерный массив. Если выбранный вами формат ввода не указывает каким-либо образом ширину или высоту карты, вы можете принять дополнительные аргументы для них (вы должны четко указать это в своем ответе). Вы можете смешивать аргументы командной строки и стандартный ввод, если он вам подходит (например, карта из stdin, минимальная вероятность успеха из argv). Ниже приведены примеры действительных и недействительных карт.

Действительно:

o
|

Действительно:

  #     #
  !   o #
  !   | #
#########

Неверно (нет беглеца):

  #     #
  !     #
  !     #
#########

Неверно (беглец всегда начинает стоять):

  #     #
  !     #
  !   % #
#########

Неверный (недопустимый символ):

  #     #
  !  ~  #
  !     #
#########

Неверно (не прямоугольник / строки разной длины):

  #     #
  !   o #
  !   | # 
#########

Вы можете предположить, что ваш ввод действителен (мне все равно, что делает ваша программа, если ему передан неверный ввод).

Выход

Вывод текста (ASCII). Может быть возвращено в виде строки или напечатано на стандартный вывод. План должен быть ограничен LF, CRLF или LFCR. Точно так же после Обязательного Усилия должен быть другой LF, CRLF или LFCR. Трейлинг разрыв строки не является обязательным.

Вы должны вывести оптимальный план вместе с требуемым усилием или «Надежды нет!» если такого плана не существует. Вам не нужно выводить вероятность успеха. Этот текст может иметь или не иметь разрыв строки в конце.

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

Формат:

Required Effort: <effort>
<plan>

Например, для ввода

50
  #     #
  !   o #
  !   | #
#########

Соответствующий вывод будет:

Required Effort: 23
Step Left
Step Left
Step Left
Kick Left
Punch Left
Step Left
Step Left
Step Left
Step Left

Вероятность успеха здесь составляет 76,5%.

Для той же карты, но с минимальной вероятностью успеха в 80%, вам придется «положить в нее спину», что потребует больше усилий, но соответствует критерию вероятности успеха. Если минимальная вероятность успеха была больше 80%, вам нужно было бы подумать немного усерднее (пробить или ударить часть двери и вылезти наружу). Если бы минимальная вероятность успеха составляла 100%, вам пришлось бы распечатать «Надежды нет!»

Примеры

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

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

100
o
|

Выход:

Required Effort: 0
Drop

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

5
# =      #
# =      !
# = !  ! !
# =#######
# =      #
# =   o  #
# = ! |  #
##########

Выход:

Required Effort: 57
Step Left
Kick Left
Step Left
Step Left
Step Left
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
High Jump Right
Long Jump Right
Step Right
Drop
Kick Right
Crouch
Shuffle Right
Shuffle Right

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

60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

Выход:

Required Effort: 58
Step Left
Kick Left
Crouch
Shuffle Left
Shuffle Left
Stand
Punch Left
Clamber Up Left
Shuffle Left
Drop (Stand)
Kick Left
Crouch
Shuffle Left
Shuffle Left

Для той же карты, но 80%, результат должен быть:

There is no hope!

Для той же карты, но 50%, Требуемое усилие становится 56 с другим планом)

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

50
#######################
#          #     =    #
!          #     =    !
#          #     =    #
######  #####!## =### #
#=   ##       #  =    #
#=#############  =    #
#=               =    #
#= o             =    #
#!!|             =    #
#######################

Выход:

Required Effort: 121
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
Long Jump Left
Step Left
Step Left
Stamp
Drop
Drop
Crouch
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Stand
Clamber Up Left
Stand
Clamber Up Left
Stand
Step Left
Step Left
Step Left
Step Left
Punch Left
Clamber Up Left
Shuffle Left

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

66
######
#  ###
#o ! !
#| ! !
### ##
######

Выход:

Required Effort: 37
Step Right
Put your back into it! Right
Kick Right
Crouch
Shuffle Right
Shuffle Right

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

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

30
###################
# ## # # #   #  = #
! ## #   #   #  = #
#      #   #    = #
##  ############= #
# ## #         #= #
# =  #         #= #
! =  #         #= #
# =  #         #= #
#o=  !          ==#
#|=  !           =#
#!= # ==########==#
#   #    !   !!  =#
#   #    !!  !  = #
#   # !!!!#########
#   # #           #
#   # #           #
###################

Выход с ограничением вероятности успеха 30:

Required Effort: 199
Long Jump Right
Put your back into it! Right
<snip>

Выход с ограничением шанса успеха 32:

Required Effort: 200
Long Jump Right
Punch Right
<snip>

Используя карту сверху в качестве входных данных с вероятностью успеха 1%, вы должны получить обязательное усилие 116 (шанс успеха ~ 32%, на выполнение моей тестовой программы ушло около 20 секунд).

Критерии Победы

Это код-гольф, пусть победит самый короткий код.

Чтобы иметь право, ваша функция или программа должны работать и иметь возможность решать каждый из приведенных выше тестовых случаев менее чем за 30 минут на приемлемой машине. Мой решатель делает их каждый менее чем за 30 секунд. Если тестовый сценарий (ниже) выполняется менее чем через 30 минут, вам, безусловно, хорошо.

Пример Solver, Verifier, Test Script и TestCases (с решениями)

Код C # для решателя и верификатора решения доступен здесь как гист . Суть также содержит file.txt, который является машиночитаемой (достаточной) формой действий, описанных выше, и необходим для запуска программы. Любое расхождение между этим файлом и спецификацией не является преднамеренным.

Суть также содержит ряд тестовых случаев (включая все приведенные выше примеры) и сценарий PowerShell для автоматического запуска представления против них. Если скрипт сообщает вам, что определенный тест не пройден, вы можете запустить, OfficeEscapeSolver.exe testcase<n>.txt outputFromYourProgram.txtчтобы увидеть больше деталей. Примеры решений для этих тестов приведены в другом Gist .

Весь код представляет собой полный беспорядок (хотя и не обманут), но вам не нужно уходить далеко от того, static void Main(...)чтобы изменить количество выводимой информации (не стесняйтесь использовать эту информацию, я предоставил ее в вашу пользу!).

Прохождение тестового примера не обязательно означает, что ваш вывод правильно сформирован, так как скрипт и верификатор очень щедры. Ваш вывод должен соответствовать спецификации выше, чтобы ваше представление было действительным.

Если вы считаете, что нашли ошибку с решателем или тестовым сценарием, ошибкой в file.txtили изворотливом тестовом сценарии , то, пожалуйста, прокомментируйте этот пост или иным образом пропишите мне в SE Chat; Я, вероятно, не замечу никаких других попыток общения.

Я не буду предоставлять тестовый скрипт в Bash или Batch, потому что я их не знаю, но я рад включить перевод и напишу версию C #, если люди захотят ее.

Post Amble

Есть вопросы? Не откладывайте, спросите их сегодня!

Задача состоит в том, чтобы потребовать усилий , дать серьезным игрокам в гольф что-то, во что они могут впиться.

Спасибо ais523 за отзыв о вводе / выводе.

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

Perl 5, 1425, 1464, 1481, 1469, 1485, 1438 байт.

Это было весело! И, шокирующе, похоже, что у меня самый короткий код до 1.5kB! :)

Я уверен, что наконец-то все заработало. Используемый разделитель есть :, и есть дополнительное заполнение двух строк сверху и одного столбца с каждой стороны . Итак, для вашего ввода:

60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

моя программа будет принимать: (NB: в конце должно быть двоеточие, но не в начале!)

60
#########:# ! #   #:! ! ! o #:! # ! | #:#########:

Я использую регулярные выражения для перевода с одной карты на другую и решения с помощью грубой силы. Однако я не добавляю карты в список, если эта карта уже была достигнута с меньшими усилиями и большей или равной вероятностью. Карты удаляются из списка после исчерпания всех возможных перемещений с этой точки. Программа успешно завершается, когда она соответствует регулярному выражению, которое показывает, что я достиг боковой или нижней части, и заканчивается словами «Надежды нет!» когда список карт исчерпан.

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

Без лишних слов,

chop($P=<>,$_=<>);s/:/ : /g;$w++until/:.{$w}:/;$z=$"x$w;$_="(.{".$w--."})"for($c,$h,$i,$j);$_="$z:$z: $_$z";$n="[ =]";$d="([!#])";@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp';@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15);sub M{$_=join":",map{join'',reverse split//}split/:/};push@M,[$_,0,100,$P];$B{$_}=100;@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8);@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10);$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/';do{sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}};die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M));$e=-1;while(++$e<@M){@t=@{$M[$e]};$m=$_=$t[0];die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/);for$x(0..15){$_=$m;$t=$t[2]*$P[$x];if($G==$E[$x]+$t[1]and$t>=$t[3]*100){&$x;eval"$z Right/";A;$_=$m;M;&$x;M;eval"$z Left/";A;}}}}

Ради здравомыслия вот то же самое с символами новой строки и несколькими комментариями:

chop($P=<>,$_=<>); #Take input
s/:/ : /g; #Pad columns on either side so escapee can leave that way
$w++until/:.{$w}:/; #Find width
$z=$"x$w;#Setup a blank line for use in padding later
$_="(.{".$w--."})"for($c,$h,$i,$j); #Set up some generic capturing regexes for reuse
$_="$z:$z: $_$z"; #Pad the top and bottom so the escapee can leave those ways
$n="[ =]"; #Regex for nonsolid block
$d="([!#])"; #Regex for solid block
@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp'; #Movement names
@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";#Movement regexes
eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15); #Setup methods to apply regexes. Name of these methods are 0,1,2,3, etc, so we can easily call them in a loop
sub M{$_=join":",map{join'',reverse split//}split/:/}; #Method to mirror the map. All the regexes are right-moving, so the mirror effects are achieved by M;&$x;M
push@M,[$_,0,100,$P]; #Array for initial map position. Encodes: [Map,Effort value,Probability value 1,Probability value 2,Movements(initially undef)]. Two integers are used for the probability to avoid floating point (although after enough steps they overflow and are automatically converted to f.p.)
$B{$_}=100; #Hash map to hold best probability of reaching a map. A new map is never added if it requires at least as much effort and doesn't give a better probability.
@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8); #Effort values
@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10); #Probability values
$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/'; #Setup map values
do{ #Loop over all efforts. Do-while loop starts at undef, which is converted to zero automatically when used in a numeric context
    sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}}; #Method to add a map to list.
    die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M)); #Pares away maps that no longer can produce new maps, and prints "There is no hope!" to stderr if there are no maps left.
    $e=-1;
    while(++$e<@M){ #Loop over all maps. Note that this loops over even maps that are created during the loop
        @t=@{$M[$e]}; #Dereference info about each map
        $m=$_=$t[0]; $Setup map variables
        die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/); #Checks if escaped, and gives message if so.
        for$x(0..15){
            $_=$m; #Put map into $_
            $t=$t[2]*$P[$x]; #Probability calculation
            if($G==$E[$x]+$t[1]and$t>=$t[3]*100){ #If effort values are right and probability is over threshold
                &$x; #Run regex
                eval"$z Right/"; #Set up map info
                A; #Add map to list @M (only if probability works out right)
                $_=$m;
                M;&$x;M; #Same thing, but mirrored now (generates movement left)
                eval"$z Left/";
                A;
            }
        }
    }
}while(++$G)

Я уже вижу пару мест, чтобы сократить еще несколько байтов, но я пока не хочу снова проходить все тестирование. Позже! :)

Изменить: Добавлены некоторые отступы ниже, чтобы более точно соответствовать вашему выводу при выходе через этаж. Удалены некоторые ошибки, поэтому код теперь может работать быстрее!

Изменить: не правильно обрабатывать лестницы и падения Все еще не совсем правильно разбирается в лестницах ... Попытка исправить это сейчас.

C # 1814 1481 1395 байт

Что за наглость !! Я действительно очень доволен этим сейчас!

using C=System.Console;using System.Linq;class S{string M,N="";int x,y,E,c;decimal P=1;static void Main(){int W=0,H=0,x,i,j,k,X,Y,f,m,P=int.Parse(C.ReadLine());string l,M="",B,R="There is no hope!";for(;(l=C.ReadLine())!=null;H++,M+=l)W=l.Length;x=M.IndexOf("|");var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();for(var N=D.ToDictionary(s=>R,s=>D);D.Count>0;D.Sort((z,w)=>z.E-w.E)){S s=D[f=0];D.Remove(s);var n=N[l=s.x+s.M+s.y+s.c]=N.ContainsKey(l)?N[l]:new S[0].ToList();if(n.All(o=>o.P<s.P|o.E>s.E)){n.Add(s);X=s.x;Y=s.y;if((X|Y|-X/W-Y/H)<0){R="Required Effort: "+s.E+s.N;break;}for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(',');f<26;){l=A[k=f*3%48];B=A[++k]+(f>15?" Right":f>9?"":" Left");M=A[++k];m=f++/16*2-1;var Q=s.M.ToArray();var K=s.P*l[4]>=P&s.c==l[k=0]%2;for(j=Y-3;j++<=Y;)for(i=X;i!=X+m*M.Length/4;i+=m)if((K&="==  *!!##*!*=*|*| o*o ".Contains(""+((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ')+M[k]))&M[k++]==33)Q[x]=' ';if(K)D.Add(new S{M=new string(Q),N=s.N+"\n"+B,x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100});}}}C.Write(R);}}

Попробуйте онлайн

Завершить программу, принимает ввод в STDIN, вывод в STDOUT. По сути, переписать мой оригинальный решатель, используя простой и неэффективно реализованный BFS, чтобы найти оптимальный путь. Это достаточно быстро, не может быть намного медленнее, чем моя другая реализация (хотя я на самом деле не рассчитал это время), безусловно, работает в установленные сроки. Большую часть стоимости составляет таблица действий, которая кодируется в виде отдельных значений запятых, в которых записывается имя, карта соответствия / совпадения и другие свойства каждого доступного действия.

Начинается с чтения с минимальной вероятностью успеха и карты. Затем он находит беглеца, удаляет его с карты и создает «состояние поиска», содержащее эту информацию. Затем он выполняет BFS, которая с минимальными усилиями повторно просматривает следующее состояние выполнения (гарантируя, что находит оптимальное решение). Прежде чем развернуть узел, он сравнивает свои усилия и вероятность успеха с предыдущими узлами с той же картой и местоположением спасателя и отклоняет себя, если уже найден лучший маршрут к этому состоянию. Если он переживет это, он добавит себя в «видимую» таблицу, чтобы впоследствии он мог отклонить состояние. Это все для производительности, и без этого фактор ветвления был бы огромным. Затем он проверяет, не сбежал ли сбежавший с карты. Если это так, то это выигрывает! Он отслеживает состояние (каждое предыдущее состояние записывается с каждым состоянием) и строит план (в обратном порядке) перед выходом из цикла BFS. В противном случае он пытается применить каждое действие и добавляет любое, которое можно применить кdue очередь, перед сортировкой этой очереди, чтобы мы получили состояние наименьшего усилия на следующей итерации.

Отформатированный и закомментированный код:

using C=System.Console;
using System.Linq;

// ascii
//   32
// ! 33
// = 61
// . 46
// * 42
// # 35
// | 124
// 0 48

class S // SearchState
{
    string M, // map
        N=""; // plan
    int x, // pos x
        y, // pos y
        E, // effort
        c; // crouching?
    decimal P=1; // chance (Probability)

    static void Main()
    {
        int W=0, // map width
            H=0, // map height
            x, // various temps
            i, // local x
            j, // local y
            k, // position in match/smash map
            X, // s.x
            Y, // s.y

            // action loop
            f, // T idx
            m, // A idx, action mirror (direction)

            P=int.Parse(C.ReadLine()); // probability of success constraint

        string l, // line, Act 'block' params, map hash, match pairs; all sorts!
            M="", // initial map
            B, // name of action
            R="There is no hope!"; // result string

        // read map
        for(;(l=C.ReadLine())!=null; // while there is input to read
            H++,M+=l) // increment height, and append to M
            W=l.Length; // record width

        // detect the escapee
        x=M.IndexOf("|");

        // create first state, and add it to Due list
        var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();

        // 'seen' table, stores all the states we've been in which looked similar
        for(var N=D.ToDictionary(s=>R,s=>D); // these values are meaningless (and necessarily can't interfere), we just use it to save having to spec the type
            D.Count>0; // keep going until we run out of states to expand (-> no escape)
            D.Sort((z,w)=>z.E-w.E)) // enforce Breadth First Search
        {
            // get next State to expand, and remove it from Due
            S s=D[f=0];
            D.Remove(s);

            // retrieve or create seen list
            var n=N[l=s.x+s.M+s.y+s.c]= // store it, and cache it, l is 'hash', containing map and escapee state
                N.ContainsKey(l)? // already got a seen list for ths map?
                N[l]: // then use it!
                new S[0].ToList(); // otherwise create a new (empty) one

            // perf: only proceed if we havn't seen this map with better Effort and Chance yet
            if(n.All(o=>o.P<s.P|o.E>s.E))
            {
                // record that we have been seen
                n.Add(s);
                X=s.x;
                Y=s.y;

                if((X|Y|-X/W-Y/H)<0) // check if we our outside the bounds - this took 2.5hour to write. 1 byte.
                { // quit if both are positive or both are negative
                    // freedom
                    R="Required Effort: "+s.E+s.N;

                    // finished
                    break;
                }

                // [Crouch,Effort,dx,dy,Probability],Name,MatchSmash (first 10 are mirrors)
                // 0110d,Step,*** * #*,
                // 0110d,Climb off,=** * =*,
                // 3310d,Shuffle,***** #*,
                // 2:1/_,Clamber Up,*** *##*,
                // 0420_,Short Jump,****  *  #**,
                // 0730K,Long Jump,*****   *   #***,
                // 0<1/Z,High Jump,  * **#*,
                // 0D20P,Put your back into it!,****! *! #**,
                // 0800Z,Punch,***!**#*,
                // 0800U,Kick,*****!#*,
                // 0001d,Drop,*** ,
                // 1001d,Drop (Stand),*** ,
                // 2200d,Crouch,***#,
                // 1400d,Stand,* *#,
                // 020/d,Climb Up,=***,
                // 0800Z,Stamp,***!

                // attempt to expand this node with every action
                for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(','); // Act string
                    f<26;) // read A into T // (cycle over first 10 twice, making them mirrors)  (very convieniently, 3*16==48=='0'==x!)
                {
                    // 'parse' next action
                    l=A[k=f*3%48]; // [Effort,Crouch,dx,dy,Probability]
                    B=A[++k]+(f>15?" Right":f>9?"":" Left"); // action name
                    M=A[++k]; // Match and Smash table (4x?, escapee at 0,2, #: solid, !: smashable (and is smashed), .: empty,  : don't care, =: climable)
                    //c=l[1]-48; // crouching transition (0: standing -> standing, 1: crouching -> standing, 2: standing -> crouching, 3: crouching -> crouching)
                    m=f++/16*2-1;

                    // this will be the new map
                    var Q=s.M.ToArray();

                    // K is whether we are allowed to apply this action
                    var K=s.P*l[4]>=P& // within chance limit
                        s.c==l[k=0]%2; // crouching matches

                    // compare the map to the Match/Smash map, to make sure we can apply this transform (and smash any ! we meet)
                    for(j=Y-3;j++<=Y;) // for the 4 rows
                        for(i=X;i!=X+m*M.Length/4;i+=m) // for each column (a.M has height 4, but variable width)
                            if((K&= // K still true?
                                "==  *!!##*!*=*|*| o*o ".Contains(""+ // check for an allowed pairing (cache pairing in M) (this includes the escapee, much cheaper to do this than remove him)
                                    ((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ') // we are within bounds and match, we are out of bounds (empty)
                                    +M[k])) // char from MatchSmash map
                                &M[k++]==33) // if it is destructible ('!' == 33)
                                Q[x]=' '; // then blank it out (x is necessarily set by the cell check)

                    if(K) // if K holds
                        D.Add(new S{M=new string(Q),N=s.N+"\n"+B, // assemble plan as we go (this will chew up memory, but none of the problems are big enough for it to matter)
                            x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100}); // add the resulting state to Due
                }
            }
        }

        C.Write(R);
    }
}