Hidup Anda bisa bergantung pada ini. Jangan berkedip. Jangan berkedip. Berkedip dan Anda mati. Mereka cepat. Lebih cepat dari yang Anda bisa percaya. Jangan berbalik, jangan memalingkan muka, dan jangan berkedip! Semoga berhasil.

Menangis Malaikat adalah ras alien yang tidak bisa bergerak sambil diamati oleh makhluk lain (bahkan Malaikat lain). Mereka memberi makan dengan mengirim para korban mereka kembali ke masa lalu. Anda ( Dokter ) terperangkap di sebuah ruangan bersama beberapa orang, dan Anda perlu mendatangi TARDIS Anda.

Tugas

Tulis sebuah program yang akan, diberi representasi ASCII dari ruang persegi panjang, menghasilkan jalur yang akan membawa Anda ke tempat yang aman. Jika ada Malaikat yang dapat menyerang - kapan saja selama kemajuan Anda - maka jalan itu tidak aman. Malaikat dapat menyerang jika ia dapat melihat Anda sementara tidak terlihat oleh Anda atau Malaikat lain.

Memasukkan

Input adalah dua bagian. Pertama, arah yang Anda hadapi (NSEW). Kemudian pada baris berikutnya, representasi ruangan, menunjukkan lokasi awal / akhir, dan lokasi / menghadap semua Malaikat.

Sampel di bawah ini menunjukkan bahwa ada satu malaikat menghadap ke barat, dan Anda mulai menghadap ke selatan.

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

• . - Ruang kosong
• D - Dokter (posisi awal)
• T - TARDIS (posisi akhir)
• N,S,E,W - Seorang Malaikat, menghadap ke arah yang ditentukan (utara, selatan, timur, barat)

Pandangan

Anda dapat melihat ruang apa pun dengan 45 derajat arah yang Anda hadapi. Garis pandang terhalang jika ada entitas lain di sepanjang horisontal, vertikal, atau diagonal 45 derajat langsung. Diagonal lainnya tidak menghalangi pandangan. Garis pandang malaikat bekerja dengan cara yang sama. Misalnya, berikut ini, -mewakili bidang pandang Anda, dengan asumsi Anda menghadap ke selatan.

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

Keluaran

Outputnya adalah string yang mewakili jalur yang akan Anda ambil untuk keluar. Jika ada beberapa jalur aman, pilih salah satunya. Jika tidak ada jalur yang aman, hasilkan 0. Jika peta salah bentuk, lakukan apa pun yang Anda suka, termasuk mogok. Anggap itu cacat jika ruangan itu tidak persegi panjang, tidak ada jalan keluar, dll. Jika tidak ada Malaikat, itu tidak cacat, cukup mudah.

Untuk setiap langkah, Anda dapat melakukan salah satu dari dua hal: bergerak ke arah NSEW, atau beralih ke arah NSEW (tanpa mengubah posisi). Untuk bergerak, cukup keluarkan huruf untuk arah itu. Untuk berbalik menghadap arah, output Fdiikuti oleh huruf yang sesuai. Misalnya, output berikut:

SSFESSSSSSSW

adalah jalur aman untuk sampel yang diberikan di bagian input. Anda bergerak ke selatan dua kali, menghadap ke timur untuk menjaga agar malaikat itu tidak terlihat, lalu bergerak ke selatan tujuh kali dan ke barat sekali untuk memasuki TARDIS.

Uji Kasus

1) Kamu bisa berkeliling Malaikat yang menghadap ke timur untuk sampai ke TARDIS. Kecuali Anda melangkah langsung di antara mereka, mereka mengunci satu sama lain di tempat, jadi tidak masalah ke arah mana Anda menghadap pada titik mana pun.

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

2) Anda kalah. Tidak ada cara untuk melewati mereka. Mereka dapat saling bertemu sampai Anda melangkah di antara mereka. Pada saat itu, Anda tidak dapat menghadapi mereka berdua dan selesai. Lebih baik tutup saja matamu dan selesaikan.

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

Kemenangan

Aturan dan celah golf standar berlaku, paling tidak byte menang. Saya akan mencoba untuk mendapatkan beberapa lagi test case segera, tetapi jangan ragu untuk menyarankan Anda sendiri untuk sementara waktu.

^{Gambar dan kutipan dari 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"

Input harus disediakan seperti ini:

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

Pada dasarnya pendekatan ini diterapkan untuk menemukan semua keadaan (posisi dan arah) yang dapat dijangkau oleh Dokter dengan aman, menyimpan bagaimana dia sampai di sana dan mencetak jalan jika berhasil. Posisi dan arahan diwujudkan dengan bilangan kompleks.

Saya mungkin bisa mengamankan beberapa karakter menggunakan aritmatika bilangan kompleks Sage, tetapi itu akan berlangsung sangat lama.

Saya pertama kali berpikir saya bisa menyelamatkan enam karakter dengan membuat Dokter berubah menjadi arah tertentu setelah mencapai Tardis, tetapi saya menyadari bahwa ini dapat menghasilkan solusi yang salah. Saya juga pertama kali salah membaca aturan.

Berikut ini adalah versi yang sebagian besar tidak bercabang:

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"

Uji Kasus

Uji kasus 1:

SSSFSWWWSSSSFWEFSEFWE

Uji kasus 2:

0

Kasus uji VisualMelon:

SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

C # 1771 2034 1962 1887 1347bytes

Menulis ulang LOS pemblokiran yang memeriksa dalam 1 loop, membuatnya jauh lebih rapi, dan sekitar 450bytes lebih pendek

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

Ini adalah program lengkap yang mengharapkan input untuk diakhiri dengan EOF dan diteruskan ke STDIN. Ini (semoga) mencetak jalur terpendek ke TARDIS, atau "0" jika tidak ada jalur. Ia menggunakan Breadth First Search yang jelek untuk mengikuti semua rute yang mungkin, kemudian melakukan backtracks dari TARDIS ke The Doctor untuk mengumpulkan output.

Kode yang diformat:

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

Keluaran misalnya input

SFESWSSSSSSS

Output untuk test case 1)

WSWSWSSSESESE

Output untuk test case 2)

0

Saya mempersembahkan, seperti yang diminta, test case baru:

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

Output program saya

SESESESESFNSSSSWW

WozzeC's Test Case 1:

EEEEFWSSSFNWWN

WozzeC's Test Case 2:

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

Baik. Jadi saya memutuskan untuk mencobanya, dan anak laki-laki itu perlu waktu. Itu dibangun sebagian besar menggunakan operator logis.

• Utara = 1 = N
• Selatan = 2 = S
• Timur = 4 = E
• Barat = 8 = W
• Dokter = 6 = D
• TARDIS = 5 = T
• 15 =. <-Semua ruang kosong

Untuk menghindari keharusan memeriksa Null dll. Saya memutuskan untuk menggunakan bidang [MAX_SIZE * 3] * [MAX_SIZE] * 3 dan meletakkan papan permainan dekat dengan pusat.

Pengecekan loop dilakukan di dalam dan luar hingga 50 (MAX_SIZE). Jadi sesuatu seperti ini:

22222
21112
21D12
21112
22222

Ketika EWS atau N ditemukan, saya melakukan pemeriksaan yang sama pada bagian mereka. Jika ada yang ditemukan melihat Malaikat (Bukan Dokter) mereka mengembalikan 15 sebagai bagian gratis. Jika tidak diperhatikan, mereka kembali dengan cara apa yang harus dihadapi Dokter agar aman. yaitu N akan mengembalikan 2 untuk selatan. Kecuali jika NW atau NE dalam hal ini akan mengembalikan 6 (2 + 4) dan 10 (2 + 8) masing-masing.

Jika dua malaikat mengawasi Dokter, nilai balik dari ini adalah "ANDed" sehingga dalam contoh uji 2 posisi crunch 4 AND 8 akan berubah menjadi 0. Berarti posisi itu buruk dan harus dihindari.

Kode yang diperluas:

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

Hasil tes

1 Contoh: FNSSSWNNNWSSWSSSSENENESES

2 Contoh: Tidak ada jalan keluar

Contoh VisualMelon: FNSSSSSSSWNNNNNNWSSSSSSSSSESEEE

Kasus Tes Saya1: FSSENEEEFWSSFNSWWN

Kasus Tes Saya2: FSEEEESFWSSSSFNWWWWNFENNFSEES

Seperti yang bisa dilihat, Dokter saya suka berjalan-jalan seperti douche untuk menunjukkan kepada para malaikat betapa menyenangkannya bergerak. Saya dapat membuat perangkat lunak menemukan jalur terpendek, tetapi membutuhkan waktu lebih lama dan membutuhkan lebih banyak kode.

Uji kasus untuk kalian

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

Yang lainnya:

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