Twoje życie może zależeć od tego. Nie mrugaj. Nawet nie mrugaj. Mrugnij i nie żyjesz. Oni są szybcy. Szybciej niż możesz w to uwierzyć. Nie odwracaj się, nie odwracaj wzroku i nie mrugaj! Powodzenia.

Płaczące anioły to obca rasa, która nie może się poruszać, gdy jest obserwowana przez inną istotę (nawet innego anioła). Karmią się, wysyłając swoje ofiary z powrotem w czasie. Ty ( Doktor ) jesteś uwięziony w pokoju z niektórymi i musisz dostać się do swojego TARDIS.

Zadanie

Napisz program, który, biorąc pod uwagę reprezentację ASCII prostokątnego pokoju, wygeneruje ścieżkę, która doprowadzi cię do bezpieczeństwa. Jeśli jakikolwiek Anioł może zaatakować - w dowolnym momencie podczas postępu - ścieżka ta nie jest bezpieczna. Anioł może zaatakować, jeśli może cię zobaczyć, gdy nie jesteś widziany przez ciebie ani innego anioła.

Wejście

Wejście składa się z dwóch części. Po pierwsze, kierunek, w którym jesteś zwrócony (NSEW). Następnie na kolejnych liniach reprezentacja pokoju, pokazująca początkowe / końcowe lokalizacje oraz lokalizację / oblicze wszystkich Aniołów.

Poniższy przykład pokazuje, że jest jeden anioł skierowany na zachód, a ty zaczynasz patrzeć na południe.

S
..........
....D.....
..........
..........
..........
..........
..........
..........
.........W
..........
...T......

• . - Pusta przestrzeń
• D - Doktor (pozycja początkowa)
• T - TARDIS (pozycja końcowa)
• N,S,E,W - Anioł skierowany w określonym kierunku (północ, południe, wschód, zachód)

Linia wzroku

Możesz zobaczyć dowolną przestrzeń z kątem 45 stopni w kierunku, w którym patrzysz. Linia wzroku jest zasłonięta, jeśli na bezpośredniej poziomej, pionowej lub 45-stopniowej przekątnej znajduje się inny byt. Każda inna przekątna nie zasłania widoku. Linia wzroku aniołów działa w ten sam sposób. Na przykład poniżej -przedstawia twoje pole widzenia, zakładając, że patrzysz na południe.

........
...D....
..---...
.-----..
-------.
---N----
---.--N-
---.----

Wynik

Dane wyjściowe to ciąg znaków reprezentujący ścieżkę, którą przejdziesz do wyjścia. Jeśli istnieje wiele bezpiecznych ścieżek, wybierz dowolną. Jeśli żadna ścieżka nie jest bezpieczna, wyjście 0. Jeśli mapa jest zniekształcona, rób co chcesz, włączając awarię. Uważaj, że jest zniekształcony, jeśli pokój nie jest prostokątny, nie ma wyjścia itp. Jeśli nie ma Aniołów, nie jest zniekształcony, po prostu łatwe.

Dla każdego kroku możesz zrobić jedną z dwóch rzeczy: przesuwać się w kierunku NSEW lub skręcać w kierunku NSEW (bez zmiany pozycji). Aby się poruszać, po prostu wypisz literę dla tego kierunku. Aby obrócić się w stronę kierunku, Fwydrukuj odpowiednią literę. Na przykład następujące dane wyjściowe:

SSFESSSSSSSW

jest bezpieczną ścieżką dla próbki podanej w sekcji wprowadzania. Poruszasz się dwa razy na południe, twarzą na wschód, aby mieć anioła w zasięgu wzroku, a następnie siedem razy na południe i raz na zachód, aby wejść do TARDIS.

Przypadki testowe

1) Możesz okrążyć wschodniego anioła, aby dostać się do TARDIS. Jeśli nie przejdziesz bezpośrednio między nimi, zablokują się one na swoim miejscu, więc nie ma znaczenia, w którą stronę patrzysz w dowolnym momencie.

W
...D....
........
........
........
.E.....W
........
........
...T....

2) Przegrywasz. Nie da się ich ominąć. Widzą się, dopóki nie przejdziesz między nimi. W tym momencie nie możesz stawić im czoła i gotowe. Równie dobrze może po prostu zamknąć oczy i skończyć z tym.

S
...D....
........
........
........
E......W
........
........
...T....

Zwycięski

Obowiązują standardowe zasady gry w golfa i luki , wygrywa najmniej bajtów. Postaram się wkrótce uzyskać więcej przypadków testowych, ale w międzyczasie możesz zaproponować własne.

^{Zdjęcie i cytat z Doctor Who.}

Python - 559 565 644 633

M=input()
I=1j
Q={"S":I,"N":-I,"E":1,"W":-1}
A=[]
e=enumerate
for y,l in e(M[2:].split()):
 for x,c in e(l):
    P=x+y*1j
    if c=="D":D=(P,Q[M[0]])
    elif c=="T":T=P
    elif c!=".":A+=[(P,Q[c])]
def s(D,h,r=[]):
 def L(X,p,d):
    S=[p+d*(i+j*I)for i in range(x+y)for j in range(-i+1,i)if j]
    for f in[1,1+I,1-I]:
     i=0
     while i<x+y>1>(S[-1]in[a[0]for a in[D]+A]+[T])*i:i+=1;S+=[p+i*f*d]
    return X[0]in S
 if y>=D[0].imag>=(D[0]in[a[0]for a in A])<all(any(L(a,*b)for b in[D]+A)for a in A if L(D,*a))>(D in r)<=D[0].real<=x:
    r+=[D]
    if D[0]==T:print h;exit()
    for n in"SWEN":s((D[0]+Q[n],D[1]),h+n,r);s((D[0],Q[n]),h+"F"+n,r)
s(D,"")
print"0"

Dane wejściowe należy podać w następujący sposób:

"W\n...D....\n........\n........\n........\nE......W\n........\n........\n...T....\n"

Zasadniczo jest to podejście stosowane do znajdowania wszystkich stanów (pozycji i kierunku), do których Doktor może bezpiecznie dotrzeć, zapamiętywania, jak się tam dostał i drukowania drogi w przypadku sukcesu. Pozycje i kierunki są realizowane za pomocą liczb zespolonych.

Prawdopodobnie mógłbym uratować niektóre znaki przy użyciu arytmetyki liczb zespolonych Sage'a, ale trwałoby to bardzo długo.

Najpierw pomyślałem, że mogę uratować sześć postaci, każąc Doktorowi skręcić w określonym kierunku po dotarciu do Tardis, ale zdałem sobie sprawę, że może to doprowadzić do złych rozwiązań. Również najpierw źle odczytałem zasady.

Oto wersja w większości nie golfowa:

Map = input()

I = 1j
string_to_dir = {"S":I,"N":-I,"E":1,"W":-1}

Angels = []
Pos = 0
direction = string_to_dir[Map[0]]
for y,line in enumerate(Map[2:].split()):
    for x,char in enumerate(line):
        Pos = x+y*1j
        if char == "D":
            Doctor = (Pos, direction)
        elif char == "T":
            Tardis = (Pos, direction)
        elif char != ".":
            Angels += [(Pos,string_to_dir[char])]

reachables = []

def display(LoS, Doctor):
    string = ""
    for y,line in enumerate(Map[2:].split()):
        for x,char in enumerate(line):
            if x+y*1j == Doctor[0]:
                string += "D"
            elif x+y*1j in LoS:
                if char in ".D":
                    string += "*"
                else:
                    string += "X"
            elif char != "D":
                string += char
            else:
                string += "."

        string += "\n"
    print string

def LoS(angel,Doctor):
    p,d = angel
    Sight = []
    for i in range(x+y):
        for j in set(range(-i+1,i))-{0}:
            Sight += [p+d*i+d*j*I]
    for line in [d, (1+I)*d, (1-I)*d]:
        for i in range(1,x+y):
            Pos = p + i*line
            Sight += [Pos]
            if Pos in [angel[0] for angel in Angels+[Doctor, Tardis]]:
                break
    return Sight

def search(Doctor, history):
    global reachables

    Sight = sum([LoS(angel, Doctor) for angel in [Doctor]+Angels],[])

    if (
                all(angel[0] in Sight for angel in Angels if Doctor[0] in LoS(angel, Doctor))
            and not (Doctor in reachables)
            and (0<=Doctor[0].imag<=y)
            and (0<=Doctor[0].real<=x)
            and (Doctor[0] not in [angel[0] for angel in Angels])
        ):

        reachables += [Doctor]

        if Doctor[0] == Tardis[0]:
            print history
            exit()
        for new_direction in "SWEN":
            search((Doctor[0]+string_to_dir[new_direction], Doctor[1]), history + new_direction)
            search((Doctor[0], string_to_dir[new_direction]), history + "F" + new_direction)

search(Doctor, "")
print "0"

Przypadki testowe

Przypadek testowy 1:

SSSFSWWWSSSSFWEFSEFWE

Przypadek testowy 2:

0

Przypadek testowy VisualMelon:

SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

C # 1771 2034 1962 1887 1347 bajtów

Ponownie napisałem blokujące sprawdzanie LOS w 1 pętli, dzięki czemu jest dużo bardziej uporządkowane i około 450 bajtów krótsze

using C=System.Console;using T=System.Math;struct P{int x,y,d;static void Main(){int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;var R=C.In.ReadToEnd().Replace("\r","");var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];for(;o<h;o++)for(i=0;i<w;i++)if((M[i,o]=R[o+o*w+i])==68)M[x=i,y=o]=e;System.Func<int,int,int,bool>S=null;S=(X,Y,D)=>{var Z="SSSE_WNNNE_W___E_W";int I=0,H=0,L=0,J=Y,K=M[X,Y],B;M[X,Y]=D>0?D:K;for(H=0;H<9;H++)for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;){if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))goto W;if(B!=e)break;}for(B=I=-1;++I<w;B=1)for(J=0;J<h;J++)if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))goto W;W:M[X,Y]=K;return B>1;};P a,p=new P{x=x,y=y,d=v};var A=new System.Collections.Generic.List<P>();System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};q();for(o=0;(O=A.Count)!=o;o=O)for(i=O;i-->o;){p=A[i];if((E=M[p.x,p.y])==84)for(R="";;p=a){i=0;n:a=A[i++];O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);if(O==1&p.d==a.d)R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;else if(O<1)R="F"+(char)p.d+R;else goto n;if(i<2)goto Z;}if(E==e){if(p.x-->0)q();p.x+=2;if(p.x<w)q();p.x--;if(p.y-->0)q();p.y+=2;if(p.y<h)q();p.y--;for(F=0;F<4;q())p.d="NESW"[F++];}}R="0";Z:C.WriteLine(R);}}

Jest to kompletny program, który oczekuje, że dane wejściowe zakończą się EOF i zostaną przekazane do STDIN. (Miejmy nadzieję) wypisuje najkrótszą ścieżkę do TARDIS, lub „0”, jeśli ścieżka nie istnieje. Używa tandetnego Wyszukiwania szerokości, aby podążać wszystkimi możliwymi trasami, a następnie cofa się z TARDIS do Doktora, aby zebrać dane wyjściowe.

Sformatowany kod:

using C=System.Console;
using T=System.Math;

struct P
{
    int x,y,d;

    static void Main()
    {
        int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;
        var R=C.In.ReadToEnd().Replace("\r","");
        var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];

        for(;o<h;o++)
            for(i=0;i<w;i++)
                if((M[i,o]=R[o+o*w+i])==68)
                    M[x=i,y=o]=e;

        System.Func<int,int,int,bool>S=null;
        S=(X,Y,D)=>
        {
            var Z="SSSE_WNNNE_W___E_W";

            int I=0,H=0,L=0,J=Y,K=M[X,Y],B;
            M[X,Y]=D>0?D:K;

            for(H=0;H<9;H++)
                for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;)
                {
                    if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))
                        goto W;
                    if(B!=e)
                        break;
                }

            for(B=I=-1;++I<w;B=1)
                for(J=0;J<h;J++)
                    if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))
                        goto W;
        W:
            M[X,Y]=K;
            return B>1;
        };

        P a,p=new P{x=x,y=y,d=v};
        var A=new System.Collections.Generic.List<P>();
        System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};
        q();

        for(o=0;(O=A.Count)!=o;o=O)
            for(i=O;i-->o;)
            {
                p=A[i];
                if((E=M[p.x,p.y])==84)
                    for(R="";;p=a)
                    {
                        i=0;
                    n:
                        a=A[i++];

                        O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);
                        if(O==1&p.d==a.d)
                            R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;
                        else if(O<1)
                            R="F"+(char)p.d+R;
                        else goto n;

                        if(i<2)
                            goto Z;
                    }
                if(E==e)
                {
                    if(p.x-->0)q();
                    p.x+=2;if(p.x<w)q();p.x--;
                    if(p.y-->0)q();
                    p.y+=2;if(p.y<h)q();p.y--;

                    for(F=0;F<4;q())
                        p.d="NESW"[F++];
                }
            }
        R="0";
    Z:
        C.WriteLine(R);
    }
}

Wyjście na przykład dane wejściowe

SFESWSSSSSSS

Dane wyjściowe dla przypadku testowego 1)

WSWSWSSSESESE

Dane wyjściowe dla przypadku testowego 2)

0

Na żądanie przedstawiam nowy przypadek testowy:

S
..E..DS....
...........
...........
...........
...........
...........
...........
...........
....SSSSS.W
.......T...

Mój program generuje

SESESESESFNSSSSWW

Przypadek testowy 1 WozzeC:

EEEEFWSSSFNWWN

Przypadek testowy 2 WozzeC:

FSEEEESFWSSSSWFNWWWNFENNEES

C # 1454, 1396, 1373, 1303 1279

class P{static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;static string[,]t=new string[o,o];static int[,]m=new int[o,o];static string e=" NS ETD W      .",q="0";static void Main(string[]s){m[0,1]=m[1,8]=-1;m[0,2]=m[1,4]=1;u=e.IndexOf(s[0][0]);for(;k<s[0].Length;k++){var c=s[0][k];if(c=='D'){X=x;Y=y;}if(c=='\\'){y++;x=d;k++;}else m[y,x++]=e.IndexOf(c);}k=A(X,Y,1);if((k&u)!=0){W(X,Y,k,"");}System.Console.Write(q);}static void W(int x,int y,int h,string s){t[y,x]=s;for(int i=1;i<9;i*=2){int l=y+m[0,i],g=x+m[1,i];if(m[l,g]==5)q=t[l,g]=s+e[i];else if(m[l,g]==15){m[l,g]=6;m[y,x]=15;int n=A(g,l,1),U;for(int j=1;j<9;j*=2){var z=t[l,g]??s;if((n&h&j)!=0&z.Length>=s.Length){U=u;u=j;W(g,l,n,s+((u!=j)?"F"+e[j]:"")+e[i]);u=U;}}m[y,x]=6;m[l,g]=0;}}}static int A(int x,int y,int L){int r=15,a,b,c,f=0,g,h,R,B;for(a=1;a<d-5;a++){g=1;for(b=y-a;b<=y+a;b++)for(c=x-a;c<=x+a;c++){B=m[b,c];R=0;bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V;if(B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0)){h=R;if(b==y-a){R=1;if(c==x-a){h=4;R=9;}else if(c==x+a){h=8;R=5;}B&=h&2;}else if(b==y+a){R=2;if(c==x-a){h=4;R=10;}else if(c==x+a){h=8;R=6;}B&=h&1;}else if(c==x-a){B&=4;R=8;}else if(c==x+a){B&=8;R=4;}else B=0;if(B!=0){if(L==1&&A(c,b,0)==15)r&=R;if(L==0)return R;}}if(z){if(B<9&B>0&!(c==x&y==b))f|=g;g*=2;}}}return r;}}

Dobrze. Postanowiłem więc spróbować, a chłopak zajął trochę czasu. Jest zbudowany głównie za pomocą operatorów logicznych.

• Północ = 1 = N
• Południe = 2 = S
• Wschód = 4 = E
• Zachód = 8 = W
• Lekarz = 6 = D.
• TARDIS = 5 = T
• 15 =. <-Wszystkie wolne miejsca

Aby uniknąć konieczności sprawdzania wartości Null itp., Postanowiłem użyć pola [MAX_SIZE * 3] * [MAX_SIZE] * 3 i umieściłem planszę blisko środka.

Sprawdzanie pętli jest wykonywane wewnątrz i na zewnątrz do 50 (MAX_SIZE). Więc coś takiego:

22222
21112
21D12
21112
22222

Kiedy zostanie znaleziony EWS lub N, robię to samo z ich strony. Jeśli coś zostanie znalezione patrząc na Anioły (nie Doktora), zwracają 15 jako wolne przejście. Jeśli nie zostaną na nie popatrzeni, wracają, w którą stronę Lekarz powinien być bezpieczny. tzn. N zwróci 2 na południe. Chyba że jest to NW lub NE, w którym to przypadku zwróci odpowiednio 6 (2 + 4) i 10 (2 + 8).

Jeśli dwa anioły obserwują Doktora, zwracane przez nie wartości byłyby „AND”, więc w przykładzie testowym 2 crunchpozycje 4 i 8 zmieniłyby się w 0. Oznacza to, że pozycja jest zła i należy jej unikać.

Rozszerzony kod:

class P
{
    static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;
    static string[,] t = new string[o, o];
    static int[,] m = new int[o, o];
    static string e = " NS ETD W      .", q="0";
    static void Main(string[]s)
    {   
        m[0, 1]=m[1, 8]=-1;
        m[0, 2]=m[1, 4]=1;
        u=e.IndexOf(s[0][0]);
        for (;k<s[0].Length;k++)
        {
            var c = s[0][k];
            if (c == 'D') { X = x; Y = y; }
            if (c == '\\') { y++; x = d; k++; }
            else m[y, x++] = e.IndexOf(c);
        }
        k=A(X,Y,1);
        if ((k&u)!=0)
        {
            W(X, Y, k,"");
        }
        System.Console.Write(q);
    }
    static void W(int x,int y,int h,string s){
        t[y, x] = s;
        for (int i = 1; i < 9; i*=2)
        {
            int l = y+m[0, i], g = x+m[1, i];
            if (m[l, g] == 5)
                q = t[l, g] = s + e[i];
            else if (m[l, g] == 15)
            {
                m[l, g] = 6;
                m[y, x] = 15;
                int n = A(g, l,1),U;
                for (int j = 1; j < 9; j *= 2)
                {
                    var z = t[l, g]??s;
                    if ((n & h & j) != 0 & z.Length>=s.Length)
                    {
                        U = u;
                        u = j;
                        W(g, l, n,s+((u != j) ? "F" + e[j] : "") + e[i]);
                        u = U;
                    }
                }
                m[y, x] = 6;
                m[l, g] = 0;
            }
        }
    }
    static int A(int x, int y,int L)
    {
        int r = 15,a,b,c,f=0,g,h,R,B;
        for (a = 1; a < d - 5; a++)
        {
            g = 1;
            for (b = y - a; b <= y + a; b++)
                for (c = x - a; c <= x + a; c++)
                {
                    B=m[b, c];
                    R=0;
                    bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V; 
                    if (B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0))
                    {
                        h=R;
                        if (b==y-a)
                        {
                            R=1;
                            if(c==x-a){h=4;R=9;}
                            else if(c==x+a){h=8;R=5;}
                            B&=h&2;
                        }
                        else if (b==y+a)
                        {
                            R=2;
                            if(c==x-a){h=4;R=10;}
                            else if (c==x+a){h=8;R=6;}
                            B&=h&1;
                        }
                        else if(c==x-a){B&=4;R=8;}
                        else if(c==x+a){B&=8;R=4;}
                        else B=0;
                        if (B!=0)
                        {
                            if(L==1&&A(c,b,0)==15)r&=R;
                            if (L==0)return R;
                        }
                    }
                    if (z)
                    {
                        if (B < 9 & B > 0 & !(c==x&y==b))
                           f |= g;
                        g *= 2;
                    }
                }
        }
        return r;
    }
}

Wyniki testu

1 Przykład: FNSSSWNNNWSSSWSSSSENNESES

2 Przykład: Nie ma wyjścia

Przykład VisualMelon: FNSSSSSSSWNNNNNNNWSSSSSSSSSEEEE

Mój przypadek testowy 1: FSSENEEEFWSSFNSWWN

Mój przypadek testowy 2: FSEEEESFWSSSSFNWWWWNFENNFSEES

Jak widać, mój Doktor uwielbia włóczyć się po okolicy, aby pokazać Aniołom, jak fajnie jest się poruszać. Mogę sprawić, że oprogramowanie znajdzie najkrótszą ścieżkę, ale zajmuje to więcej czasu i potrzebuje więcej kodu.

Testy dla was

S
D....
..NE.
.WTS.
.S...

Inny:

E
D....
WNNN.
...E.
.WTE.
.SSE.
.....