빙산에 좌초 된 과학자 물개 일반 봉인입니다.) 출력 설명 씰이 어떻게

소개

물개 가족이 북극권의 빙산에 좌초됩니다. 씰이 도움을 요청하는 데 사용할 수있는 무선 송신기가 빙산에 있습니다. 그러나 아빠 봉인 만 무선 송신기 작동 방법을 알고 있습니다. 더 나쁜 것은, 올해이시기에 얼음이 매우 미끄러 워서 물개가 다른 물개에 부딪 치거나 빙산의 가장자리에서 미끄러 져 나올 때까지 물개가 제어 할 수 없게 미끄러 져서 아빠 물개가 라디오 송신기에 도달하기가 매우 어렵다는 것입니다. 운 좋게도 인감 중 하나는 컴퓨터 과학자이므로 아빠 인감을 무선 송신기로 조작하는 방법을 알아내는 프로그램을 작성하기로 결정했습니다. 프로그램을 작성할 공간이 많지 않기 때문에 프로그램은 가능한 적은 바이트를 사용하도록 결정합니다.

입력 설명

봉인 프로그램은 STDIN, 명령 행 인수 또는 사용자 입력 함수 (예 :)에서 입력을받습니다 raw_input(). 변수에서 사전 초기화 할 수 없습니다 (예 : “이 프로그램은 변수의 입력을 예상합니다 x“).

입력의 첫 번째 줄은 쉼표로 구분 된 두 개의 정수 형식으로 구성됩니다 

A,B

그 뒤에는 각각 문자 B로 구성된 줄 이 있습니다 A. 각 줄은 다음 중 문자 만 포함 할 수 있습니다.

  • .: 추위, 추위, 바다. 지도에는 항상 테두리가 있습니다.
  • #: 빙산의 일부.
  • a… z: 빙산의 아빠 물개가 아닌 물개.
  • D: 아빠가 빙산에 봉인.
  • *: 무선 송신기.

(아빠 봉인은 항상 대문자로 표시 D됩니다. 소문자 d는 단순히 일반 봉인입니다.)

출력 설명

씰이 어떻게 움직일 수 있는지에 관한 다음 규칙에 따라, 씰을 무선 송신기로 가져 오기 위해 씰을 어떻게 움직여야하는지에 대한 지시 목록을 출력하십시오.

  1. 규칙 : 모든 씰은 위 ( U), 아래 ( D), 왼쪽 ( L) 및 오른쪽 ( R)으로 이동할 수 있습니다 . 대각선으로 미끄러질 수 없습니다.
  2. 규칙 : 물개가 움직이면 물개가 다른 물개와 충돌하거나 바다로 떨어질 때까지 같은 방향으로 계속 움직입니다.
    1. 씰이 다른 씰과 충돌하면 움직이지 않습니다. 충돌 한 봉인은 움직이지 않습니다 .
    2. 바다 표범이 바다로 떨어지면 익사하여지도에서 사라집니다. 즉, 다른 씰의 충돌체 역할을하지 않으며 다시 이동할 수 없습니다.
  3. 규칙 : 두 개의 봉인은 동시에 이동할 수 없으며 다른 봉인이 여전히 움직이고있는 동안에는 봉인을 이동할 수 없습니다. 다음 씰은 이전 씰의 이동이 중지 된 후에 만 ​​이동할 수 있습니다.
  4. 규칙 : 물개를 여러 번 움직이거나 익사하는 물개 수에 대한 제한은 없습니다.
  5. 규칙 : 올바른 해결책은 무선 송신기에서 아빠 밀봉이 끝날 것 입니다. 아빠 물개는 미끄러지는 동안 단순히 송신기를 통과 할 수 없습니다 .

출력은 여러 줄로 구성되며 각 줄은

A,B

여기서 A(이동 시일이다 D아빠 씰, a… z등을위한), 및 B(하나 시일을 이동하는 방향이고 U, D, L, 또는 R). 당신이주의 가장 짧은 경로를 찾을 필요가 없습니다. 아빠 인감을 목표로하는 모든 경로는 허용 가능한 출력입니다.

입력 및 출력 예

입력:

25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................

산출:

D,R

입력:

9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........

출력 (많은 것 중 하나의 가능한 출력) :

m,R
b,L
D,U
D,R
D,D
D,L

입력:

26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................

출력 (많은 것 중 하나의 가능한 출력) :

v,D
D,L

다른 질문이 있으시면 의견을 보내주십시오.

답변

파이썬 3, 520 바이트

R=range
g=[list(input())for i in R(int(input().split(',')[1]))]
f=set(sum(g,[]))-set(".#*")
L=8
def P(p,g):
 if len(p)>L:return
 for s in f:
  c=sum(y.index(s)for y in g if s in y)
  if c<1:continue
  r,=[n for n in R(len(g))if s in g[n]]
  for d in R(4):
   m=p+s+",%s\n"%"LURD"[d];G=[y[:]for y in g];o="#";i,j=I,J=r,c
   while"#"==o:G[i][j]="#";G[I][J]=s;i,j=I,J;I,J=i+d%2*(d-2),j+(~d%-2&d-1);o=G[I][J]
   if"."==o:G[i][j]="#"
   if"D"==s:
    if"."==o:continue
    if"*"==o:print(m);1/0
   P(m,G)
while 1:P("",g);L+=4

사람들이 원하는 경우 나중에 더 자세한 설명을 할 수 있지만 기본적으로 가능한 이동의 상태 공간을 반복적으로 심화 하면서 깊이 우선 검색을 실행 합니다. 이동으로 아빠 물개가 떨어지면 즉시 거부됩니다. 아빠가 송신기 옆에 있으면 이동 순서가 인쇄되고 프로그램은 0으로 나눠 종료합니다.

if G!=g:두 번째 마지막 줄의 시작 부분에 8 바이트 를 추가하여 코드를 훨씬 빠르게 실행할 수 있습니다 k,L. 이는 첫 번째 테스트 사례 와 같이 아무것도 변경되지 않는 동작을 거부합니다 .

런타임은 동일한 입력으로도 실행마다 눈에 띄게 변합니다. 아마도 set정렬되지 않은 유형 인을 반복하여 이동할 다음 씰을 선택했기 때문입니다 . 두 번째 테스트 케이스의 시간을 5 분 30 초로 설정했지만 처음 실행했을 때 그리 오래 걸리지 않았습니다. 위에서 언급 한 최적화로 40 초와 같습니다.

답변

자바 스크립트 (ES6) (322) 334 (323)

Edit2 스 니펫에 애니메이션 추가

편집하다버그 수정을 하고 ‘*’의 초기 위치를 기억하므로 씰이 미끄러 져서 지워도 찾을 수 있습니다.

입력 문자열을 매개 변수로 사용하여 함수로 구현되었습니다 (아마 유효하지 않지만 설명을 기다리는 중). 팝업을 통한 출력.
JavaScript에서 여러 줄로 된 문자열 입력의 문제점은prompt 은 잘 관리되지 않는다는 것입니다.

알고리즘 : BFS는 최적의 솔루션을 찾아야합니다. 나는 게임 상태 대기열을 변수로 유지하고 l, 상태는 캐릭터 그리드 g와 지금까지의 이동 순서입니다 s. 게다가, 지금까지 변수로 얻은 그리드 세트가 있습니다.k 같은 그리드를 반복해서 탐색하는 것을 피하기 위해 .

메인 루프는

  • 게임 상태를 빼다
  • 모든 가능한 이동을 시도하고, 유효한 각 이동 후 상태를 큐에 넣습니다 (IIF 결과 그리드가 아직 존재하지 않음)
  • 솔루션이 발견되면 루프를 종료하십시오.
F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,'']],k=[];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  alert(t)
}

Snippet을 실행하여 FireFox에서 테스트

코드 스 니펫 표시

F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,k=[]]];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  return t
}

$('.T td').each(function(i,td) { $('.R td').eq(i).text(F($(td).text())) });

$(".R").on('click','td',function(){
  var i = $(this).index();
  var $td = $('.T td').eq(i);
  var t = $td.text().trim();
  animate($td, $td.text().trim(), $('.R td').eq(i).text().trim());
});

$('#GO').on('click',function() {
  var s = T0.value, h=F(s)
  console.log(s)
  $('#R0').text(h);
  animate($('#A'), s,h);
});

function animate($out, s, h){
  o=~s.match(/\d+/),g=[...s.replace(/.*/,'')];

  fr=[g.join('')];
  h.replace(/.,(.)/g, (c,d)=>{
    i = g.indexOf(c=c[0]);
    d = [-1,1,o,-o]['LRUD'.search(d)]
    for(;g[i+d]<'.';i+=d)
    {
      g[i]='#',z=[...g],g[i+d]=c,z[i+d]='<b>'+c+'</b>', fr.push(z.join(''))
    }
    if(g[i+d]=='.')
    {
      g[i]='#', fr.push(g.join(''))
    }
  })

  var fa = ()=>{
    var f=fr.shift();
    f ? $out.html(f) : (
      clearInterval(i),
      $out.text(s),
      $out.toggleClass('Anim')
  )};
  $out.toggleClass('Anim');
  fa();
  var i=setInterval(fa, 500);
}
td { vertical-align: top; font-family: monospace; white-space: pre; }
textarea { width: 99%;  height:10em;}
pre { margin: 0; }
.R td { background: #fdc; padding: 6px 0; }
.R td:hover { background: #ffc }
.T td { background: #ddf}
B { color: red }
.T td.Anim, td.Anim { background: #ffc; }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table cellspacing=5>
  <tr>
    <th colspan=4>Predefined tests</th>
  </tr>
  <tr class=T>
    <td>25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................</td>
    <td>9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........</td>
<td>26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................</td>
<td>8,5
........
.##c###.
.a#*#D#.
.##b###.
........</td>
    </tr>
  <tr><td colspan=4>Click on solution text to start animation</td>
  </tr>
  <tr class=R>
    <td></td><td></td><td></td><td></td>
  </tr>
  <tr><th colspan=2>Your test  </th></tr>
  <tr><td colspan=2><textarea id=T0></textarea></td>
    <td colspan=2 id=A></td>
  </tr>
  <tr>
    <td colspan=2>Find solution and animate <button id=GO>go</button></td>
    <td colspan=2 id=R0></td>
  </tr>
</table>
스 니펫 확장

답변

C ++, 628 바이트

글쎄, 이것은 매우 짧지 않았다 :

#include <set>
#include <iostream>
using namespace std;struct R{string b,m;bool operator<(R r)const{return b<r.b;}};int w,h,t,j,k,z=1;char c,f;set<R> p,q;int m(R r,int x,int d,char a){for(j=x,c=r.b[x];(f=r.b[j+=d])==35;);if(c-68||f-46){r.b[x]=35;if(f-46)r.b[j-d]=c;r.m+=c;r.m+=44;r.m+=a;r.m+=10;if(c==68&j-d==t){cout<<r.m;z=0;}if(p.count(r)+q.count(r)==0){q.insert(r);}}}int main(){cin>>w>>c>>h>>c;R r;string l;for(;k++<h;){getline(cin,l);r.b+=l;}t=r.b.find(42);r.b[t]=35;q.insert(r);for(;z;){r=*q.begin();q.erase(q.begin());p.insert(r);for(k=0;z&&k<w*h;++k){if(r.b[k]>64){m(r,k,-1,76);m(r,k,1,82);m(r,k,-w,85);m(r,k,w,68);}}}}

데이터 구조 ( set, string) 를 사용하고 싶었 기 때문에 C ++을 선택 했지만 본질적으로 매우 장황합니다. 이 솔루션은 성능면에서 합리적으로 뛰어나 런타임에 최적화되지 않았더라도 MacBook Pro에서 2 초 조금만에 테스트 2를 해결합니다.

공백 및 다른 길이 감소를 제거하기 시작하기 전에 코드 :

#include <set>
#include <iostream>

using namespace std;

struct R {
    string b, m;
    bool operator<(R r) const {return b < r.b; }
};

int w, h, t;
set<R> p, q;
bool z = true;

void m(R r, int k, int d, char a) {
    int j = k;
    char s = r.b[k], f;
    for (; (f = r.b[j += d]) == 35;);
    if (s - 68 || f - 46) {
        r.b[k] = 35;
        if (f - 46) {
            r.b[j - d] = s;
        }
        r.m += s;
        r.m += 44;
        r.m += a;
        r.m += 10;
        if (s == 68 && j - d == t) {
            cout << r.m;
            z = false;
        }
        if (p.count(r) + q.count(r) == 0) {
            q.insert(r);
        }
    }
}

int main() {
    char c;
    cin >> w >> c >> h >> c;
    string b, l;
    int k;
    for (k = 0; k < h; ++k) {
        getline(cin, l);
        b += l;
    }

    t = b.find(42);
    b[t] = 35;

    R r;
    r.b = b;
    q.insert(r);

    for ( ; z; ) {
        r = *q.begin();
        q.erase(q.begin());
        p.insert(r);

        for (k = 0; z && k < w * h; ++k) {
            c = r.b[k];
            if (c > 64) {
                m(r, k, -1, 76);
                m(r, k, 1, 82);
                m(r, k, -w, 85);
                m(r, k, w, 68);
            }
        }
    }

    return 0;
}

알고리즘의 핵심 아이디어는 두 세트가 유지된다는 것입니다.

  • q 처리 대기중인 구성 세트입니다.
  • p 처리 된 구성 세트입니다.

알고리즘은의 초기 구성으로 시작합니다 q. 모든 단계에서 구성이에서 q추가되고에 추가되고 p가능한 모든 씰 이동이 생성되고 새 구성이에 삽입됩니다 q.

시운전 :

bash-3.2$ ./a.out <test1
D,R
bash-3.2$ time ./a.out <test2
p,U
c,U
p,R
c,L
m,L
b,L
a,L
D,U
b,L
D,R
D,D
D,L

real    0m2.267s
user    0m2.262s
sys 0m0.003s
bash-3.2$ ./a.out <test3
v,U
D,L
bash-3.2$

답변