Ваша жизнь может зависеть от этого. Не моргай Даже не моргай. Моргни и ты мертв. Они быстрые. Быстрее, чем ты можешь поверить. Не отворачивайся, не отводи взгляд и не моргай! Удачи.

Плачущие Ангелы - это инопланетная раса, которая не может двигаться, пока ее наблюдает другое существо (даже другой Ангел). Они питаются, отправляя своих жертв назад во времени. Вы ( Доктор ) попали в комнату с некоторыми, и вам нужно попасть в ТАРДИС.

задача

Напишите программу, которая при представлении ASCII прямоугольной комнаты выведет путь, который приведет вас к безопасности. Если любой Ангел может атаковать - в любое время во время вашего прогресса - тогда этот путь небезопасен. Ангел может атаковать, если он видит вас, когда вы не замечены ни вами, ни другим Ангелом.

вход

Вход состоит из двух частей. Во-первых, направление, с которым вы сталкиваетесь (NSEW). Затем в последующих строках - представление о комнате с указанием местоположения начала / конца и местоположения / облицовки всех Ангелов.

Пример ниже показывает, что есть один ангел, смотрящий на запад, и вы начинаете смотреть на юг.

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

• . - Пустое пространство
• D - Доктор (исходная позиция)
• T - ТАРДИС (конечная позиция)
• N,S,E,W - Ангел, смотрящий в указанном направлении (север, юг, восток, запад)

Поле зрения

Вы можете увидеть любое пространство под углом 45 градусов в том направлении, в котором вы находитесь. Линия обзора затруднена, если есть другой объект по прямой горизонтальной, вертикальной или 45-градусной диагонали. Любая другая диагональ не мешает обзору. Линия зрения ангелов работает точно так же. Например, в следующем, -представляет ваше поле зрения, предполагая, что вы обращены на юг.

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

Выход

Выводом является строка, представляющая путь, по которому вы пойдете, чтобы выйти. Если существует несколько безопасных путей, выберите любой. Если ни один путь не является безопасным, выведите 0. Если карта искажена, делайте все, что угодно, в том числе сбой. Считайте, что это уродливо, если комната не прямоугольная, нет выхода и т. Д. Если нет Ангелов, это не уродливо, просто легко.

Для каждого шага вы можете сделать одно из двух: двигаться в направлении NSEW или поворачиваться в направлении NSEW (не меняя положения). Для перемещения просто выведите букву для этого направления. Чтобы повернуться лицом к направлению, выведите Fсоответствующую букву. Например, следующий вывод:

SSFESSSSSSSW

является безопасным путем для образца, указанного в разделе ввода. Вы двинетесь на юг дважды, поверните на восток, чтобы держать ангела в поле зрения, затем двиньтесь на юг еще семь раз и на запад один раз, чтобы войти в ТАРДИС.

Тестовые случаи

1) Вы можете обойти ангела, обращенного на восток, чтобы добраться до ТАРДИС. Если вы не встанете прямо между ними, они заблокируют друг друга на месте, поэтому не имеет значения, в каком направлении вы находитесь в любой точке.

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

2) Вы проигрываете. Нет способа пройти мимо них. Они могут видеть друг друга, пока вы не встанете между ними. В этот момент вы не можете столкнуться с ними обоими, и все готово. Можно просто закрыть глаза и покончить с этим.

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

выигрыш

Применяются стандартные правила игры в гольф и лазейки , выигрывает минимум байт. Я постараюсь в ближайшее время получить еще несколько тестов, но не стесняйтесь предлагать свои собственные.

^{Изображение и цитата из Доктора Кто.}

Питон - 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"

Ввод должен быть представлен следующим образом:

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

По сути, именно этот подход применяется для нахождения всех состояний (положения и направления), которые Доктор может благополучно достичь, запоминания того, как он туда попал, и распечатывания пути в случае успеха. Позиции и направления реализуются с помощью комплексных чисел.

Я мог бы, вероятно, сохранить некоторые символы, используя сложную арифметику Мудреца, но это будет очень долго.

Сначала я подумал, что смогу спасти шесть символов, заставив Доктора повернуть в определенном направлении после достижения Тардис, но я понял, что это может привести к неправильным решениям. Также я сначала неправильно понял правила.

Вот в основном негольфированная версия:

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"

Тестовые случаи

Тестовый пример 1:

SSSFSWWWSSSSFWEFSEFWE

Контрольный пример 2:

0

Тестовый пример VisualMelon:

SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

C # 1771 2034 1962 1887 1347 байт

Переписал блокировку проверки LOS за 1 цикл, сделав ее намного более аккуратной и примерно на 450 байт короче

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

Это полная программа, которая ожидает, что ввод завершится EOF и будет передан в STDIN. Он (надеюсь) печатает кратчайший путь к ТАРДИС или «0», если пути не существует. Он использует некачественный поиск в ширину, чтобы следовать всем возможным маршрутам, а затем возвращается назад от ТАРДИС к Доктору, чтобы собрать выходные данные.

Форматированный код:

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

Вывод для примера ввода

SFESWSSSSSSS

Выход для тестового примера 1)

WSWSWSSSESESE

Выход для теста 2)

0

По запросу я представляю новый тестовый пример:

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

Моя программа выводит

SESESESESFNSSSSWW

Тестовый пример WozzeC 1:

EEEEFWSSSFNWWN

Тестовый пример WozzeC 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;}}

Правильно. Поэтому я решил попробовать, и мальчик занял какое-то время. Он построен в основном с использованием логических операторов.

• Север = 1 = N
• Юг = 2 = S
• Восток = 4 = E
• Запад = 8 = ш
• Доктор = 6 = D
• ТАРДИС = 5 = Т
• 15 = <-Все свободные места

Чтобы не проверять наличие нулевого значения и т. Д., Я решил использовать поле [MAX_SIZE * 3] * [MAX_SIZE] * 3 и расположить игровое поле ближе к центру.

Циклические проверки выполняются внутри и снаружи до 50 (MAX_SIZE). Так что-то вроде этого:

22222
21112
21D12
21112
22222

Когда EWS или N найдены, я делаю ту же проверку с их стороны. Если что-то найдено, глядя на Ангелов (не Доктора), они возвращают 15 в качестве свободного прохода. Если на них не смотрят, они возвращаются, и Доктор должен быть в безопасности. то есть N вернул бы 2 на юг. Если это не NW или NE, в этом случае он вернет 6 (2 + 4) и 10 (2 + 8) соответственно.

Если двое ангелов наблюдают за Доктором, возвращаемые значения будут «И», поэтому в тестовом примере 2 положения 4 И 8 будут превращаться в 0. Это означает, что позиция плохая и ее следует избегать.

Расширенный код:

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

Результаты теста

1 Пример: FNSSSWNNNWSSSWSSSSENNESES

2 Пример: выхода нет

Пример VisualMelon: FNSSSSSSSWNNNNNNNWSSSSSSSSSEEEE

Мой тестовый случай1: FSSENEEEFWSSFNSWWN

Мой тестовый пример2: FSEEEESFWSSSSFNWWWWNFENNFSEES

Как видно, мой Доктор любит ходить, как душ, чтобы показать Ангелам, как весело передвигаться. Я могу заставить программное обеспечение найти кратчайший путь, но это занимает больше времени и требует больше кода.

Тестовые случаи для вас, ребята

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

Другой:

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