펄 216 215 바이트

에 +2 포함 -0p

STDIN에 입력하십시오. 사용하여 %, 외부 벽에 대해 #내부 벽을위한 0빈 공간에 대한 8생쥐과 r시작 위치에 대한. 전체 보드는 사각형을 형성하도록 채워 져야합니다. 다음과 같이 예제를 변환하고 실행할 수 있습니다.

cat dynamite.txt | perl -p0e 's/.+/$a^=$&/egr;s//sprintf"%-*s",length$a,$&/eg;1while/\n/,s/^ *\K#|#(?= *$)|^ *.{@{-}}\K#|\A[^\n]*\K#|#(?=[^\n]*\n\z)|#(?=.{@{-}} *$)/%/sm;y/ EM/0x2/' | dynamite.pl

dynamite.pl:

#!/usr/bin/perl -0p
sub f{@a{@_}||=push@{$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)},@_}f$_;for(@{$%}){f y/xr|/ytx/r;{f s/\pL\d/$&^(E&$&)x2/er}{f s/(q|s|y)#/$&^"\x01\x13"/er}my$o;{$\|=/x/>/2/;$o.="
"while s/.$/$o.=$&,""/meg}f$o}$%++>999|$\||redo}{

\xhh청구 된 점수 의 이스케이프를 교체하십시오 .

이 프로그램은 복잡한 경우를 현실적으로 처리 할 수 ​​없습니다. 특히 실패 사례를 처리 할 수 ​​없습니다. 내부 벽을 날려 버리거나 마우스를 집어 올리는 방법이 너무 많기 때문에 같은 상태를 여러 번 처리 할 수 ​​없을 정도로 똑똑하더라도 검색이 너무 넓어지고 너무 많은 메모리를 사용하기 때문입니다. 100약간 견딜 수있는 런타임 및 메모리 사용을 위해 압력 제한을 낮추어야 합니다.

설명

필드의 상태를 나타 내기 위해 문자의 비트 패턴을 사용합니다.

contains victim: 0000 0010
has hero:        0100 0000
carry dynamite   0000 0001
carry mouse      0000 0100
home             0000 1000
walkable         0001 0000 (not really needed but results in shorter regexes)
make printable   0010 0000
wall             0010 xxxx (bit patterns not very important,
permawall        0010 xxxx  just avoid letters and digits)

예를 들어 01000000다이너마이트 ( )를 들고 있는 영웅 ( ) 00000001은 걸어 갈 수있는 곳에 있어야 00010000하고 ( ) 모든 값을 인쇄 가능한 ASCII ( 00100000) 로 만들고 싶습니다 . or이 모든 비트 마스크 의 비트 단위 를 취하면에 01110001대한 ASCII 코드가됩니다 q. 총체적으로 이것은 :

p: hero                     r hero on victim
q: hero carrying dynamite   s hero carrying dynamite on victim
t: hero carrying mouse      v hero carrying mouse on victim

x : hero at home
y : hero at home carrying dynamite
| : hero at home carrying mouse

0: empty  without hero
8: home   without hero
2: victim without hero

%: permanent wall
#: normal wall

이 프로그램은 영웅이 오른쪽으로 이동하는 것만 고려합니다 (나중에 설명하는 회전은 다른 방향을 처리합니다). 비트 마스크는 영웅이 항상 문자와 숫자로 이동할 수있는 장소로 표시되도록 신중하게 선택되었습니다 (피해자를 운반하는 집의 영웅을 제외하고는 영웅의 유일한 움직임은 떨어질 것입니다) 피해자). 따라서 앞으로 나아갈 수있는 영웅은와 일치합니다 /\pL\d/. 일치하는 부분 문자열은 영웅과 그가 가지고있는 것이 첫 번째 문자에서 제거되고 두 번째 문자에 추가되도록 수정되어야하며, xor두 문자에 대해 동일한 값 으로 비트 단위로 수행 할 수 있습니다 . xor 값은 영웅 비트 ( 01000000), 다이너마이트 비트 ( 00000001) 및 캐리 마우스 비트 ( 00000100)로 구성됩니다. 그들은 함께 or에01000101이것은 ASCII E입니다. 따라서 영웅을 움직이는 것은 :

s/\pL\d/$&^(E&$&)x2/e

영웅은 벽 바로 앞에 서서 다이너마이트 ( q, s또는 y)를 들고 있다면 벽을 날려 버릴 수 있습니다 . 영웅은 자신의 다이너 마이트를 잃게됩니다 ( xor와 00000001)과 벽은 #통로로 변경됩니다 0(와 XOR 00010011그래서)

s/(q|s|y)#/$&^"\x01\x13"/e

다른 방향을 처리하려면 전체 보드가 회전합니다 (회전 된 보드는으로 끝남 $o).

my$o;$o.="\n"while s/.$/$o.=$&,""/meg

영웅을 옮기는 것 외에도 그가 할 수있는 다른 많은 선택이 있습니다 :

When at home, pick up dynamite:                   x -> y
When on victim not carrying anything pick him up: r -> t
When at home carrying a victim, drop him off:     | -> x

이것은에 의해 수행

y/xr|/ytx/

영웅이 집에 아무것도 가지고 있지 않고 ( x) 구조 할 희생자가 더 없으면 보드가 완성됩니다 ( 2). 이것은 편리하게 테스트 할 수 있습니다

/x/>/2/

보드가 해결되면이 상태를 기억하고 마지막에 인쇄하고 싶습니다. 나는에서 “해결”플래그를 가지고 있음을 들어 $\및 인쇄하지 않고 프로그램의 마지막에 그 인쇄 $_때문에,

$\|=/x/>/2/  ...   }{

압력 0에서 처리 될 상태 @0는 압력 1 @1등에서 유지됩니다 $%. 현재 압력은 유지됩니다 . 사용 $n또는 변수가 무엇인가에 초기화되어 있지 않은 경우 autovivification 그렇지 않으면 변경됩니다 때문에 같은 짧은 될하지만 코드가 작동하지 않는 $n일정한 압력에서 상태에 대한 배열 reference.Looping로하는 것은 사용하여 수행됩니다 for아니라 map인해를 를 for사용하면 배열이 계속 반복되는 동안 배열을 확장하고 새로운 요소를 선택할 수 있습니다. 이것은 영웅의 회전과 단일 필드 선택이 0 번에 발생하고 동일한 압력 배열로 끝나기 때문에 필요합니다. 주어진 압력에 대한 루프는

for(@{$%}){...}

압력이 1000에 도달하거나 용액이 발견 될 때까지이를 반복합니다.

$%++>999|$\||redo

남은 것은 새로 발견 된 상태를 해당 압력 어레이에 추가하는 것입니다. 이는 서브 루틴에 의해 수행됩니다 f. 아직 보지 못한 상태 만 추가하려고합니다. 이전에 본 상태는 다음과 같이 유지됩니다 %a.

sub f{@a{@_}||=push@$n, @_}

$n상태에 대한 새로운 압력을 나타냅니다. 나는 정규 표현식 변수가 영웅의 행동으로 인해이 호출로 이어진다는 상태에서 파생 될 것입니다.

if $1 is set it was from s/(q|s|y)#/$&^"\x01\x13"/e which blows a wall -> 50
else if $& is set it was from s/\pL\d/$&^(E&$&)x2/e, so the hero moves.
    if $& contains 8 the hero went home -> 0
    else if the hero has carry bits (5) -> 2
    else                                   1
else ($& was not set) it was from y/xr|/ytx/r -> 0

이것은 다음과 같은 공식으로 이어집니다 $n.

$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)

모든 대체는 r수정자를 가져서 변경된 상태를 리턴하고 현재 상태를 $_단독으로 둡니다. f그런 다음이 변경된 상태에서 호출되므로 다음과 같은 코드가 표시됩니다

f y/xr|/ytx/r;

계산 $n에는 정규식 변수 가 필요 하기 때문에 대체 변수가 변경되지 않는 경우 (변수를 트리거하는 조건이 충족되지 않기 때문에) 기본적으로 설정 해제해야합니다. 또한 이전 루프에서 정규식 변수를 선택해서는 안됩니다. 따라서 대체는 {}블록으로 랩핑되어 정규식 상태를 저장하고 복원합니다. 그것이 당신이 같은 진술을 얻는 방법입니다

{f s/\pL\d/$&^(E&$&)x2/er}

특히 회전은 너무 래핑되어 f정규식 변수없이 호출 하고 압력 기여도 0을 얻습니다.

여전히 할 일은 @0시작시 초기 상태 로 프라이밍하는 것 입니다.

f$_

이것은 메인 루프에 있으므로 $_이후 압력 배열 에 추가하려고 시도 하지만 초기 상태가 이미 있으므로 %a아무 일도 일어나지 않습니다.

이 모든 것이 기본적으로 Dijkstra의 알고리즘을 사용하여 가장 짧은 솔루션을 찾습니다 . 그래도 잠재적 인 문제가 있습니다. 현재 코드는 첫 번째 발견보다 낮은 압력으로 재발견되면 상태를 추가하지 않습니다. 나는 이것을 유발할 보드를 만들 수 없었지만 그것이 불가능하다는 것을 증명할 수 없었습니다.

답변

L=[]
f=(S,r="",R="",p=0,s=S.replace(RegExp(r),R),l=`((.|\n){${s.split`
`[0].length}})`,q=p+1,o=p+2,n=p+50)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...[[/ E/,"me",q],[/ E/,"de",o],[/ME/,"ce",q],[/E /,"em",q],[/E /,"ed",o],[/EM/,"ec",q],[`E${l} `,"e$1m",q],[`E${l} `,"e$1d",o],[`E${l}M`,"e$1c",q],[` ${l}E`,"m$1e",q],[` ${l}E`,"d$1e",o],[`M${l}E`,"c$1e",q],[/ m/,"m ",q],[/m /," m",q],[`m${l} `," $1m",q],[` ${l}m`,"m$1 ",q],[/ (d|c)/,"$1 ",o],[/(d|c) /," $1",o],[`(d|c)${l} `," $2$1",o],[` ${l}(d|c)`,"$3$1 ",o],[/d#/,"m ",n],[/#d/," m",n],[`#${l}d`," $1m",n],[`d${l}#`,"m$1 ",n],[/mM/," c",q],[/Mm/,"c ",q],[`M${l}m`,"c$1 ",q],[`m${l}M`," $1c",q],[/[mc]e/," E",p],[/e[mc]/,"E ",p],[`e${l}[mc]`,"E$1 ",p],[`[mc]${l}e`," $1E",p]].map(a=>f(s,...a)))
F=s=>f(s)<1e3

stateList = []
f=(s,regex="",replacement="",pressure=0,state=s.replace(regexp(regex),replacement),line=`((.|\n){${state.split("\n")[0].length}})`)=>{
    if (state in stateList || pressure > 999) return 1e3
    if (!/M/.test(state) && /E/.test(state)) return pressure

    stateList[state] = 0

    return [
        [/ E/,"me",pressure+1],
        [/ E/,"de",pressure+2],
        [/ME/,"ce",pressure+1],
        [/E /,"em",pressure+1],
        [/E /,"ed",pressure+2],
        [/EM/,"ec",pressure+1],
        [`E${line} `,"e$1m",pressure+1],
        [`E${line} `,"e$1d",pressure+2],
        [`E${line}M`,"e$1c",pressure+1],
        [` ${line}E`,"m$1e",pressure+1],
        [` ${line}E`,"d$1e",pressure+2],
        [`M${line}E`,"c$1e",pressure+1],
        [/ m/,"m ",pressure+1],
        [/m /," m",pressure+1],
        [`m${line} `," $1m",pressure+1],
        [` ${line}m`,"m$1 ",pressure+1],
        [/ ([dc])/,"$1 ",pressure+2],
        [/([dc]) /," $1",pressure+2],
        [`([dc])${line} `," $2$1",pressure+2],
        [` ${line}([dc])`,"$3$1 ",pressure+2],
        [/d#/,"m ",pressure+50],
        [/#d/," m",pressure+50],
        [`#${line}d`," $1m",pressure+50],
        [`d${line}#`,"m$1 ",pressure+50],
        [/mM/," c",pressure+1],
        [/Mm/,"c ",pressure+1],
        [`M${line}m`,"c$1 ",pressure+1],
        [`m${line}M`," $1c",pressure+1],
        [/[mc]e/," E",pressure],
        [/e[mc]/,"E ",pressure],
        [`e${line}[mc]`,"E$1 ",pressure],
        [`[mc]${line}e`," $1E",pressure]
    ].map(a=>f(state,...a)).reduce((a,b)=>a-b<0?a:b) //reduce used for support in more browsers.
}
s=>f(s)>1e3