Wprowadzenie

Rodzina fok utknęła na górze lodowej w kole podbiegunowym. Na górze lodowej znajduje się nadajnik radiowy, za pomocą którego foki mogą wezwać pomoc. Jednak tylko pieczęć tatusia wie, jak obsługiwać nadajnik radiowy. Co gorsza, lód jest bardzo śliski o tej porze roku, więc foki będą ślizgały się w sposób niekontrolowany, dopóki nie uderzą w kolejną pieczęć lub ześlizgną się z krawędzi góry lodowej, co utrudnia tatusiowi dotarcie do nadajnika radiowego. Na szczęście jedna z pieczęci jest informatykiem, więc postanawia napisać program, aby dowiedzieć się, jak manewrować pieczęcią tatusia do nadajnika radiowego. Ponieważ na lodzie nie ma dużo miejsca na napisanie programu, postanawia sprawić, by program używał jak najmniej bajtów.

Opis wejścia

Program pieczęci pobiera dane wejściowe z STDIN, argumenty wiersza poleceń lub funkcje wprowadzania danych przez użytkownika (takie jak raw_input()). Nie można go zainicjować w zmiennej (np. „Ten program oczekuje danych wejściowych w zmiennej x”).

Pierwszy wiersz danych wejściowych składa się z dwóch liczb całkowitych oddzielonych przecinkiem w formularzu

A,B

Poniżej znajdują się Bwiersze składające się ze Aznaków. Każda linia może zawierać tylko znaki spośród następujących:

• .: Zimno, zimno, ocean. Mapa zawsze będzie miała tę granicę.
• #: Część góry lodowej.
• a... z: Pieczęć, która nie jest tatusiem na górze lodowej.
• D: Foka tatusia na górze lodowej.
• *: Nadajnik radiowy.

(Pamiętaj, że pieczęć tatusia jest zawsze oznaczona wielką Dliterą. Mała litera djest po prostu zwykłą pieczęcią).

Opis wyjścia

Zgodnie z następującymi zasadami dotyczącymi sposobu przemieszczania się pieczęci, wypisz listę instrukcji dla pieczęci, w jaki sposób powinny się one poruszać, aby dostać pieczęć tatusia do nadajnika radiowego.

1. Reguła: Wszystkie pieczęcie mogą poruszać się w górę ( U), w dół ( D), w lewo ( L) i w prawo ( R). Nie mogą się przesuwać po przekątnej.
2. Reguła: Podczas ruchu pieczęć będzie się poruszać w tym samym kierunku, aż zderzy się z inną pieczęcią lub wpadnie do morza.
   1. Jeśli pieczęć zderzy się z inną pieczęcią, przestanie się poruszać. Pieczęć, z którą zderzył się, nie będzie się poruszać.
   2. Jeśli foka wpadnie do morza, utonie i zniknie z mapy. Oznacza to, że nie działa on jako zderzacz dla innych pieczęci i nie można go ponownie przenieść.
3. Reguła: Dwie pieczęcie nie mogą się poruszać w tym samym czasie, nie można też przesunąć pieczęci, gdy inna jest w ruchu. Następną pieczęć można przenieść dopiero, gdy poprzednia pieczęć przestanie się poruszać.
4. Reguła: Nie ma ograniczeń dotyczących wielokrotnego przenoszenia pieczęci lub liczby tonących pieczęci.
5. Reguła: Prawidłowe rozwiązanie będzie miało koniec pieczęci na nadajniku radiowym. Tatuś nie może po prostu przejść nadajnika podczas przesuwania.

Wynik będzie składał się z kilku wierszy, każdy w formie

A,B

Gdzie Ajest uszczelka przenieść ( Ddla tatusia uszczelki, a... zdla innych), i Bjest to kierunek, aby przesunąć uszczelkę (albo U, D, L, lub R). Pamiętaj, że nie musisz znajdować najkrótszej trasy. Każda droga, która prowadzi pieczęć tatusia do celu, jest akceptowalnym wyjściem.

Przykładowe wejścia i wyjścia

Wejście:

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

Wynik:

D,R

Wejście:

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

Wyjście (jedno możliwe wyjście z wielu):

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

Wejście:

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

Wyjście (jedno możliwe wyjście z wielu):

v,D
D,L

Jeśli masz inne pytania, zadaj je w komentarzach.

Python 3, 520 bajtów

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

Bardziej szczegółowe wyjaśnienie mogę zrobić później, jeśli ludzie tego chcą, ale w zasadzie uruchamia to wyszukiwanie w pierwszej kolejności z iteracyjnym pogłębianiem w przestrzeni stanów możliwych ruchów. Jeśli ruch powoduje odpadnięcie pieczęci tatusia, jest on natychmiast odrzucany. Jeśli tata kończy się obok nadajnika, sekwencja ruchów jest drukowana, a program dzieli się przez zero, aby wymusić wyjście.

Mogę sprawić, że kod będzie działał znacznie szybciej, dodając if G!=g:na początku drugiego ostatniego wiersza dla 8 dodatkowych bajtów - to odrzuca ruchy, które niczego nie zmieniają, na przykład k,Lw pierwszym przypadku testowym.

Środowisko wykonawcze różni się zauważalnie w zależności od przebiegu, nawet przy tych samych danych wejściowych - najwyraźniej wynika to z faktu, że wybieram następną pieczęć, aby przejść przez iterację nad setnieuporządkowanym typem. Drugą skrzynkę testową wyregulowałem na 5 minut i 30 sekund, chociaż nie wydawało mi się, że przy pierwszym uruchomieniu tak długo to trwało. Przy wspomnianej wyżej optymalizacji, to więcej niż 40 sekund.

JavaScript (ES6) 322 334 323

Edycja2 Dodano animację we fragmencie

Edytuj poprawkę, zapamiętaj początkową pozycję „*”, więc znajduję ją nawet wtedy, gdy pieczęć zsuwa się na nią i kasuje.

Zaimplementowano jako funkcję z ciągiem wejściowym jako parametrem (prawdopodobnie niepoprawnym, ale czekającym na wyjaśnienie). Wyjście przez wyskakujące okienko.
Problem z wprowadzaniem ciągów wielowierszowych w JavaScript polega na tym, promptże nie radzi sobie z tym dobrze.

Co do algorytmu: BFS, powinien znaleźć optymalne rozwiązanie. Trzymam kolejkę statusu gry w zmiennej l, status jest oparty na siatce postaci gi sekwencji ruchów s. Poza tym istnieje zestaw siatek uzyskanych do tej pory w zmiennej k, aby uniknąć eksploracji tej samej siatki raz za razem.

Główna pętla to

• usunąć status gry
• wypróbuj wszystkie możliwe ruchy, kolejkuj status po każdym prawidłowym ruchu (IIF wynikowa siatka nie jest już obecna)
• jeśli znaleziono rozwiązanie, wyjdź z pętli

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)
}

Uruchom Snippet, aby przetestować w 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 bajtów

Cóż, nie okazało się to bardzo krótko:

#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);}}}}

Wybrałem C ++, ponieważ chciałem użyć struktur danych ( set, string), ale z natury jest dość gadatliwy. Rozwiązanie dość dobrze radzi sobie z wydajnością, rozwiązując test 2 w nieco ponad 2 sekundy na MacBooku Pro, nawet jeśli nie jest zoptymalizowany pod kątem czasu działania.

Kod, zanim zaczniesz eliminować białe znaki i niektóre inne skróty długości:

#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;
}

Podstawową ideą algorytmu jest utrzymanie dwóch zestawów:

• q to zestaw konfiguracji oczekujących na przetworzenie.
• p to zestaw przetworzonych konfiguracji.

Algorytm rozpoczyna się od początkowej konfiguracji w q. Na każdym etapie tworzona jest konfiguracja q, dodawana p, generowane są wszystkie możliwe ruchy uszczelnienia, a powstałe nowe konfiguracje wstawiane q.

Testowe uruchomienie:

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$