Roboti na útěku

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
 
namespace RobotiNaUteku
{
    class Program
    {
        const int Rozmer = 20;
        static Pozice[] Roboti = new Pozice[2];
        static bool[, ,] Bludiste = new bool[2, Rozmer, Rozmer];
        static Straz[,] Straze = new Straz[2, 10];
        static Pozice[] RozmeryBludiste = new Pozice[2];
        static int[] PocetStrazi = new int[2];
 
        enum Smery
        {
            N = 0,
            W = 1,
            S = 2,
            E = 3,
            Start,
            Unknown
        }
 
        static void Main(string[] args)
        {
            bool[, , , ,] StavovyProstor = new bool[12, Rozmer + 1, Rozmer + 1, Rozmer + 1, Rozmer + 1];
 
            NacistVstup("robots.in");
 
            Stav Zacatek = new Stav(Smery.Start, null);
            Zacatek.Robot1 = Roboti[0];
            Zacatek.Robot2 = Roboti[1];
            StavovyProstor[0, Roboti[0].Sloupec, Roboti[0].Radek, Roboti[1].Sloupec, Roboti[1].Radek] = true;
 
            Queue<Stav> Fronta = new Queue<Stav>();
            Fronta.Enqueue(Zacatek);
 
            Pozice Robot1, Robot2;
            int cas;
 
            while (Fronta.Count > 0)
            {
                Stav stav = Fronta.Dequeue();
                cas = (stav.Krok + 1) % 12;
                for (int s = 0; s < 4; s++)
                {
                    //spocitat kam dojdem timhle smerem
                    Smery posun = (Smery)s;
                    Robot1 = PosunRobota(0, stav.Robot1, posun);
                    Robot2 = PosunRobota(1, stav.Robot2, posun);
 
                    bool robotiChyceni = Chycen(0, stav.Robot1, Robot1, stav.Krok, cas) || Chycen(1, stav.Robot2, Robot2, stav.Krok, cas);
                    if (!robotiChyceni && !StavovyProstor[cas, Robot1.Sloupec, Robot1.Radek, Robot2.Sloupec, Robot2.Radek]) //nebyli
                    {
                        StavovyProstor[cas, Robot1.Sloupec, Robot1.Radek, Robot2.Sloupec, Robot2.Radek] = true;
                        //podivame se, jestli roboti nejsou venku
                        if (Robot1.Sloupec == Rozmer && Robot2.Sloupec == Rozmer)
                        {
                            VypisCestu(stav, posun);
                            return;
                        }
 
                        Stav nalezeny = new Stav(posun, cas, Robot1.Sloupec, Robot1.Radek, Robot2.Sloupec, Robot2.Radek);
                        nalezeny.Minuly = stav;
                        Fronta.Enqueue(nalezeny);
                    }
                }
            }
 
            StreamWriter sw = new StreamWriter("robots.out");
            sw.WriteLine("-1");
            sw.Close();
        }
 
        static void NacistVstup(string filename)
        {
            StreamReader sr = new StreamReader(filename);
            for (int b = 0; b < 2; b++) //bludiste
            {
                string radek = sr.ReadLine();
                string[] split = radek.Split(new char[] { ' ' });
                RozmeryBludiste[b] = new Pozice(int.Parse(split[0]), int.Parse(split[1]));
 
                //schema bludistatka
                for (int r = 0; r < int.Parse(split[0]); r++) //radky
                {
                    radek = sr.ReadLine();
                    for (int s = 0; s < int.Parse(split[1]); s++) //sloupce
                    {
                        char policko = radek[s];
                        switch (policko)
                        {
                            case '#':
                                Bludiste[b, r, s] = true; //stena true
                                break;
                            case '.':
                                Bludiste[b, r, s] = false; //volne false
                                break;
                            case 'X':
                                Roboti[b] = new Pozice(r, s);
                                break;
                        }
                    }
                }
                //straze
                string strazi = sr.ReadLine();
                PocetStrazi[b] = int.Parse(strazi);
                for (int s = 0; s < int.Parse(strazi); s++)
                {
                    radek = sr.ReadLine();
                    string[] exp = radek.Split(new char[] { ' ' });
                    Straze[b, s] = new Straz(int.Parse(exp[0]) - 1, int.Parse(exp[1]) - 1, int.Parse(exp[2]), exp[3]);
                }
            }
            sr.Close();
        }
 
        static bool Chycen(int bludiste, Pozice robotPredchozi, Pozice robotAktualni, int krokPredchozi, int krokAktualni)
        {
            if (robotAktualni.Radek == Rozmer) //pokud je venku, delalo by to problem
                return false;
 
            for (int i = 0; i < PocetStrazi[bludiste]; i++)
            {
                Straz s = Straze[bludiste, i];
                Pozice strazPredchozi = s.Umisteni(krokPredchozi, 0);
                Pozice strazAktualni = s.Umisteni(krokAktualni, 1);
                if (robotAktualni.Radek == strazAktualni.Radek && robotAktualni.Sloupec == strazAktualni.Sloupec) //pokud vlezli na spolecne policko
                {
                    return true;
                }
                if (robotAktualni.Radek == strazPredchozi.Radek && robotAktualni.Sloupec == strazPredchozi.Sloupec
                    && robotPredchozi.Radek == strazAktualni.Radek && robotPredchozi.Sloupec == strazAktualni.Sloupec) //pokud se jen prohodi navzajem
                {
                    return true;
                }
            }
            return false;
        }
 
        static void VypisCestu(Stav zpet, Smery posledni)
        {
            List<Smery> Cesta = new List<Smery>();
            Cesta.Add(posledni);
            Stav prubeh = zpet;
            while (prubeh.Prichod != Smery.Start)
            {
                Cesta.Add(prubeh.Prichod);
                prubeh = prubeh.Minuly;
            }
 
            StreamWriter sw = new StreamWriter("robots.out");
            sw.WriteLine(Cesta.Count);
            for (int o = Cesta.Count - 1; o > -1; o--)
            {
                sw.WriteLine(GetString(Cesta[o]));
            }
            sw.Close();
        }
 
        static Pozice PosunRobota(int i, Pozice robot, Smery posun)
        {
            if (robot.Sloupec == Rozmer)
            {
                return robot;
            }
            Pozice nova = new Pozice(robot.Radek, robot.Sloupec);
 
            switch (posun)
            {
                case Smery.N:
                    if (nova.Radek - 1 >= 0)
                    {
                        if (!Bludiste[i, nova.Radek - 1, nova.Sloupec])
                        {
                            nova.Radek -= 1;
                        }
                    }
                    else
                    {
                        //venku
                        nova.Radek = nova.Sloupec = Rozmer;
                    }
                    break;
                case Smery.S:
                    if (nova.Radek + 1 < RozmeryBludiste[i].Radek)
                    {
                        if (!Bludiste[i, nova.Radek + 1, nova.Sloupec])
                        {
                            nova.Radek += 1;
                        }
                    }
                    else
                    {
                        //venku
                        nova.Radek = nova.Sloupec = Rozmer;
                    }
                    break;
                case Smery.E:
                    if (nova.Sloupec + 1 < RozmeryBludiste[i].Sloupec)
                    {
                        if (!Bludiste[i, nova.Radek, nova.Sloupec + 1])
                        {
                            nova.Sloupec += 1;
                        }
                    }
                    else
                    {
                        //venku
                        nova.Radek = nova.Sloupec = Rozmer;
                    }
                    break;
                case Smery.W:
                    if (nova.Sloupec - 1 >= 0)
                    {
                        if (!Bludiste[i, nova.Radek, nova.Sloupec - 1])
                        {
                            nova.Sloupec -= 1;
                        }
                    }
                    else
                    {
                        //venku
                        nova.Radek = nova.Sloupec = Rozmer;
                    }
                    break;
            }
            return nova;
        }
 
        static char GetString(Smery s)
        {
            char d = '?';
            switch (s)
            {
                case Smery.E:
                    d = 'E';
                    break;
                case Smery.N:
                    d = 'N';
                    break;
                case Smery.S:
                    d = 'S';
                    break;
                case Smery.W:
                    d = 'W';
                    break;
            }
            return d;
        }
 
        class Pozice
        {
            public int Radek;
            public int Sloupec;
 
            public Pozice(int radek, int sloupec)
            {
                Zmen(radek, sloupec);
            }
 
            public void Zmen(int radek, int sloupec)
            {
                Radek = radek;
                Sloupec = sloupec;
            }
        }
 
        class Stav
        {
            public Pozice Robot1;
            public Pozice Robot2;
            public int Krok;
            public Smery Prichod = Smery.Unknown;
            public Stav Minuly = null;
 
            public Stav(Smery odkud, int cas, int x1, int y1, int x2, int y2)
            {
                Prichod = odkud;
                Krok = cas;
                Robot1 = new Pozice(y1, x1);
                Robot2 = new Pozice(y2, x2);
            }
 
            public Stav(Smery odkud, Stav minuly)
            {
                Prichod = odkud;
                Minuly = minuly;
            }
        }
 
        class Robot
        {
            public Pozice Pozice;
            public Robot(int radek, int sloupec)
            {
                Pozice = new Pozice(radek, sloupec);
            }
        }
 
        class Straz
        {
            public Pozice Poloha;
            public int Delka;
            public Smery Smer;
            private Pozice[] AktualniPoloha; //timhle mame globalni objekt pro straz, musi byt dva, protoze porovnavame dve pozice stejne straze ve dvou casech
 
            public Straz(int radek, int sloupec, int delka, string smer)
            {
                Poloha = new Pozice(radek, sloupec);
                AktualniPoloha = new Pozice[2] { new Pozice(radek, sloupec), new Pozice(radek, sloupec) };
                Delka = delka;
                switch (smer)
                {
                    case "N":
                        Smer = Smery.N;
                        break;
                    case "W":
                        Smer = Smery.W;
                        break;
                    case "S":
                        Smer = Smery.S;
                        break;
                    case "E":
                        Smer = Smery.E;
                        break;
                }
            }
 
            public Pozice Umisteni(int krok, int i)
            {
                int pocetPosunuti = (Delka - 1) - Math.Abs((krok % ((Delka - 1) * 2)) - Delka + 1);
                AktualniPoloha[i].Zmen(Poloha.Radek, Poloha.Sloupec);
                switch (Smer)
                {
                    case Smery.N:
                        AktualniPoloha[i].Radek -= 1 * pocetPosunuti;
                        break;
                    case Smery.S:
                        AktualniPoloha[i].Radek += 1 * pocetPosunuti;
                        break;
                    case Smery.E:
                        AktualniPoloha[i].Sloupec += 1 * pocetPosunuti;
                        break;
                    case Smery.W:
                        AktualniPoloha[i].Sloupec -= 1 * pocetPosunuti;
                        break;
                }
                return AktualniPoloha[i];
            }
        }
    }
}