C# a platforma .NET – Domáca úloha – Roboti na úteku

Súčasťou získavania zápočtu z predmetu C# a platformy .NET je aj riešenie domácich úloh. Tento semester bola domáca úloha len jedna a ani tá nebola ťažká, ale nebola ani triviálna. Jej riešenie vám teraz prinášam.

 

Najprv ale zadanie úlohy. Nepopíšm ho celé, na to je príliš dlhé, ale zhrniem len tie hlavné body:

 

Na vstupe máme súbor obsahujúci dve bludiská. V kažom bludisku stojí jeden robot a od 0 do 10 strážcov. Roboti aj stráže sa pohybujú vždy o jedno políčko a to len na jednu z hlavných svetových strán (teda žiadne diagonály). Na začiatku každého ťahu roboti dostanú signál (rovnaký pre oboch robotov), ktorým smerom sa majú pohnúť. Stráže majú svoje presne vymedzené trasy a v každom kroku sa pohnú podľa nich. Úlohou je nájsť najkraší sled signálov, ktorý oboch robotov vyvedie z bludiska bez toho, aby ich chytili stráže. Ak existuje viac riešení, stačí nájsť jedno ľubovoľné.

Upresnenie zadania:

  • Každé bludisko je veľké maximálne 20×20 políčok
  • Ak sa robot nemôže pohnúť (na políčku je stena), zostane stáť
  • Ak robot opustí bludisko, všetky ďalšie signály ignoruje
  • Súradnice políčok začínajú na políčku [1,1]
  • Stráže nemusia na svojich trasách prechádzať stenou, trasy dvoch strážcov sa môžu pretínať, ale dve stráže nikdy nebudú stáť na rovnakom políčku
  • Stráže sa pohubujú po úsečke – keď prídu na koniec trasy, otočia sa a v ďalšom kroku sa vracajú spať

Upresnenie formátu vstupného súboru (okopírované zo zadania):

  • Na prvním řádku se nachází dvě čísla Ri a Ci oddělená mezerou, která představují počet řádků (Ri) a sloupců (Ci) bludiště i.
  • Následujících Ri řádků obsahuje vždy Ci znaků, kde každý znak popisuje jedno políčko bludiště. Znak ‘#‘ představuje zeď, znak ‘.‘ volně průchozí pole a znak ‘X‘ počáteční pozici robota v bludišti.
  • Za mapou bludiště následuje řádek s jediným číslem Gi, které udává počet stráží v bludišti. Připomeňme si, že 0 ≤ Gi ≤ 10.
  • Následuje Gi řádků. Každý řádek obsahuje tři celá čísla a jeden znak oddělené mezerou a popisuje právě jednu stráž. První dvě čísla určují řádek a sloupec počátečního políčka stráže. Třetí číslo určuje délku hlídkovací trasy (v rozsahu 2..4). A konečně poslední písmeno určuje směr, kterým se stráž na začátku dívá (a kterým se také začne pohybovat). Směr je dán prvním písmenem světové strany v anglickém jazyce, tedy: N, S, E nebo W (pro North, South, East a West).

Vzorový vstup:

5 4
####
#X.#
#..#
...#
##.#
1
4 3 2 W
4 4
####
#...
#X.#
####
0

Upresnenie formátu výstupného súboru:

  • Na prvom riadku je počet potrebných signálov
  • Na každom ďalšom riadku je práve jeden signál (vyjadrený pomocou svetovej strany – N, S, E, W)
  • Ak pre daný vstup neexistuje riešenie, výstupný súbor bude obsahovať len -1

Vzorový výstup:

8
E
N
E
S
S
S
E
S

 

Trochu dlhé zadanie, že? 😀 Napriek tomu však úloha nie je věľmi zložitá. Dôležitá je časová a pamôťová zložitosť – riešenie nesmie bežať príliš dlho a môže zabrať najviac 140 MB operačnej pamäte. Niekoľko tipov:

  • Chôdza stráží sa opakuje v cykle dlhom najviac 12 krokov
  • Stavy výpočtu možno najefektívnejšie reprezentovať 5-rozmerným poľom (súradnice X a Y prvého robota, súradnice X a Y druhého robota a poloha stráži normovaná na dĺžku ich cyklov – najviac 12)

 

A tu je moje riešenie (odkaz na okomentovanú verziu pod kódom):


using System;
using System.Collections.Generic;
using System.Text;

namespace RobotiNaUteku
{
    class Program
    {
        static char[,] maze1;
        static char[,] maze2;
        static List<Guard> guards1;
        static List<Guard> guards2;
        static int[] robot1;
        static int[] robot2;
        static int multiple = 0;
        static int m1width;
        static int m1height;
        static int m2width;
        static int m2height;

        static bool[, , , ,] StateRepository;

        static void Main(string[] args)
        {
            LoadMaze();

            State start = new State(robot1[0], robot1[1], robot2[0], robot2[1]);
            StateRepository[robot1[0], robot1[1], robot2[0], robot2[1], 0] = true;

            State sn, se, ss, sw;
            State result = new State();
            Queue<State> cue = new Queue<State>();
            cue.Enqueue(start);

            while (cue.Count > 0)
            {
                State s = cue.Dequeue();
                if (s.r1x == 0 || s.r1x == m1width - 1 || s.r1y == 0 || s.r1y == m1height - 1)
                    s.r1active = false;
                if (s.r2x == 0 || s.r2x == m2width - 1 || s.r2y == 0 || s.r2y == m2height - 1)
                    s.r2active = false;
                if (!s.r1active && !s.r2active)
                {
                    result = s;
                    break;
                }
                int x1 = s.r1x;
                int y1 = s.r1y;
                int x2 = s.r2x;
                int y2 = s.r2y;

                if (s.r1active && maze1[s.r1x, s.r1y - 1] != '#')
                {
                    y1 = s.r1y - 1;
                }
                if (s.r2active && maze2[s.r2x, s.r2y - 1] != '#')
                {
                    y2 = s.r2y - 1;
                }

                sn = new State(x1, y1, x2, y2);
                sn.r1active = s.r1active;
                sn.r2active = s.r2active;
                sn.directions = s.directions + "N";

                x1 = s.r1x;
                y1 = s.r1y;
                x2 = s.r2x;
                y2 = s.r2y;

                if (s.r1active && maze1[s.r1x + 1, s.r1y] != '#')
                {
                    x1 = s.r1x + 1;
                }

                if (s.r2active && maze2[s.r2x + 1, s.r2y] != '#')
                {
                    x2 = s.r2x + 1;
                }

                se = new State(x1, y1, x2, y2);
                se.r1active = s.r1active;
                se.r2active = s.r2active;
                se.directions = s.directions + "E";

                x1 = s.r1x;
                y1 = s.r1y;
                x2 = s.r2x;
                y2 = s.r2y;

                if (s.r1active && maze1[s.r1x, s.r1y + 1] != '#')
                {
                    y1 = s.r1y + 1;
                }

                if (s.r2active && maze2[s.r2x, s.r2y + 1] != '#')
                {
                    y2 = s.r2y + 1;
                }

                ss = new State(x1, y1, x2, y2);
                ss.r1active = s.r1active;
                ss.r2active = s.r2active;
                ss.directions = s.directions + "S";

                x1 = s.r1x;
                y1 = s.r1y;
                x2 = s.r2x;
                y2 = s.r2y;

                if (s.r1active && maze1[s.r1x - 1, s.r1y] != '#')
                {
                    x1 = s.r1x - 1;
                }

                if (s.r2active && maze2[s.r2x - 1, s.r2y] != '#')
                {
                    x2 = s.r2x - 1;
                }

                sw = new State(x1, y1, x2, y2);
                sw.r1active = s.r1active;
                sw.r2active = s.r2active;
                sw.directions = s.directions + "W";

                sn.MyLast = s;
                se.MyLast = s;
                ss.MyLast = s;
                sw.MyLast = s;

                if (EvaluateState(sn))
                {
                    cue.Enqueue(sn);
                    StateRepository[sn.r1x, sn.r1y, sn.r2x, sn.r2y, sn.directions.Length % multiple] = true;
                }
                if (EvaluateState(se))
                {
                    cue.Enqueue(se);
                    StateRepository[se.r1x, se.r1y, se.r2x, se.r2y, se.directions.Length % multiple] = true;
                }
                if (EvaluateState(ss))
                {
                    cue.Enqueue(ss);
                    StateRepository[ss.r1x, ss.r1y, ss.r2x, ss.r2y, ss.directions.Length % multiple] = true;
                }
                if (EvaluateState(sw))
                {
                    cue.Enqueue(sw);
                    StateRepository[sw.r1x, sw.r1y, sw.r2x, sw.r2y, sw.directions.Length % multiple] = true;
                }
            }

            System.IO.StreamWriter writer = new System.IO.StreamWriter("robots.out");
            if (result.directions.Length == 0)
            {
                writer.Write(-1);
            }
            else
            {
                writer.WriteLine(result.directions.Length);
                foreach (char c in result.directions)
                {
                    writer.WriteLine(c);
                }
            }
            writer.Close();
            Console.ReadLine();
        }

        private static bool EvaluateState(State s)
        {
            bool notvisited = false;
            bool free = true;

            if (StateRepository[s.r1x, s.r1y, s.r2x, s.r2y, s.directions.Length % multiple] == false)
            {
                notvisited = true;
            }
            if (notvisited == true)
            {
                if (s.MyLast != null)
                {
                    foreach (Guard g in guards1)
                    {
                        int[] posnow = g.Move(s.directions.Length);
                        int[] poslast = g.Move(s.directions.Length - 1);

                        if (posnow[0] == s.r1x && posnow[1] == s.r1y)
                        {
                            free = false;
                            break;
                        }

                        if ((posnow[0] == s.MyLast.r1x && posnow[1] == s.MyLast.r1y) && (poslast[0] == s.r1x && poslast[1] == s.r1y))
                        {
                            free = false;
                            break;
                        }
                    }
                    if (free)
                    {
                        foreach (Guard g in guards2)
                        {
                            int[] posnow = g.Move(s.directions.Length);
                            int[] poslast = g.Move(s.directions.Length - 1);

                            if (posnow[0] == s.r2x && posnow[1] == s.r2y)
                            {
                                free = false;
                                break;
                            }

                            if ((posnow[0] == s.MyLast.r2x && posnow[1] == s.MyLast.r2y) && (poslast[0] == s.r2x && poslast[1] == s.r2y))
                            {
                                free = false;
                                break;
                            }
                        }
                    }
                }
            }
            return (notvisited & free);
        }

        private static int LCM(int x, int y)
        {
            if (x == 0 || y == 0) return 0;
            int tempx = x;
            int tempy = y;
            while (x != y)
            {
                if (x < y) x = x + tempx;
                else y = y + tempy;
            }

            return x;
        }

        private static void LoadMaze()
        {
            CodEx.Reader reader = new CodEx.Reader("robots.in");

            m1height = reader.Int();
            m1width = reader.Int();
            maze1 = new char[m1width + 2, m1height + 2];
            reader.Line();
            for (int i = 1; i <= m1height; i++)
            {
                for (int j = 1; j <= m1width; j++)
                {
                    char ch = reader.Char();
                    if (ch == 'X')
                        robot1 = new int[] { j, i };
                    maze1[j, i] = ch;
                }
                reader.Line();
            }

            guards1 = new List<Guard>();
            int guardcount = reader.Int();

            for (int i = 0; i < guardcount; i++)
            {
                int gy = reader.Int();
                int gx = reader.Int();
                int gl = reader.Int();
                reader.Char();
                char gd = reader.Char();
                Guard g = new Guard(gx, gy, gl, gd);
                if (multiple == 0)
                    multiple = (g.PathLength - 1) * 2;
                else
                    multiple = LCM(multiple, (g.PathLength - 1) * 2);
                guards1.Add(g);
            }
            multiple = 0;
            reader.Line();
            m2height = reader.Int();
            m2width = reader.Int();
            maze2 = new char[m2width + 2, m2height + 2];
            string s = reader.Line();
            for (int i = 1; i <= m2height; i++)
            {
                for (int j = 1; j <= m2width; j++)
                {
                    char ch = reader.Char();
                    if (ch == 'X')
                        robot2 = new int[] { j, i };
                    maze2[j, i] = ch;
                }
                s = reader.Line();
            }

            guards2 = new List<Guard>();
            guardcount = reader.Int();

            for (int i = 0; i < guardcount; i++)
            {
                int gy = reader.Int();
                int gx = reader.Int();
                int gl = reader.Int();
                reader.Char();
                char gd = reader.Char();
                Guard g = new Guard(gx, gy, gl, gd);
                if (multiple == 0)
                    multiple = (g.PathLength - 1) * 2;
                else
                    multiple = LCM(multiple, (g.PathLength - 1) * 2);
                guards2.Add(g);
            }
            reader.Close();
            if (multiple == 0) multiple = 12;
            m1height += 2;
            m1width += 2;
            m2height += 2;
            m2width += 2;
            StateRepository = new bool[m1width, m1height, m2width, m2height, multiple];
        }

        class State
        {
            public int r1x;
            public int r1y;
            public int r2x;
            public int r2y;
            public bool r1active;
            public bool r2active;
            public string directions;
            public State MyLast;

            public State(int x1, int y1, int x2, int y2)
            {
                r1x = x1;
                r1y = y1;
                r2x = x2;
                r2y = y2;
                directions = "";
                r1active = true;
                r2active = true;
                MyLast = null;
            }

            public State()
            {
                r1x = 0;
                r1y = 0;
                r2x = 0;
                r2y = 0;
                directions = "";
                r1active = true;
                r2active = true;
                MyLast = null;
            }
        }

        class Guard
        {
            public int X;
            public int Y;
            public int PathLength;
            public char Direction;
            private int division;

            private int[,] table;

            public int[] Move(int distance)
            {
                int zvysok = distance % division;
                switch (Direction)
                {
                    case 'N':
                        return new int[] { X, Y - table[PathLength - 1, zvysok] };
                        break;
                    case 'E':
                        return new int[] { X + table[PathLength - 1, zvysok], Y };
                        break;
                    case 'S':
                        return new int[] { X, Y + table[PathLength - 1, zvysok] };
                        break;
                    default:
                        return new int[] { X - table[PathLength - 1, zvysok], Y };
                        break;
                }

            }

            public Guard(int ix, int iy, int length, char d)
            {
                X = ix;
                Y = iy;
                PathLength = length;
                Direction = d;
                division = (PathLength - 1) * 2;
                table = new int[4, 6];
                table[1, 0] = 0;
                table[1, 1] = 1;
                table[2, 0] = 0;
                table[2, 1] = 1;
                table[2, 2] = 2;
                table[2, 3] = 1;
                table[3, 0] = 0;
                table[3, 1] = 1;
                table[3, 2] = 2;
                table[3, 3] = 3;
                table[3, 4] = 2;
                table[3, 5] = 1;
            }
        }
    }
}

Poznámka: program (menovite metóda LoadMaze()) využíva namespace Codex, ktorý je stavaný na mieru nášmu vyhodnocovaciem systému CodEx. Namiesto neho bude potrebné zistiť aktuálne čísla ručne (možno s použitím int.Parse() alebo niečoho podobného).

 

Archív s riešením je k dispozícii na mojom Live SkyDrive.

Reklamy

Pridaj komentár

Zadajte svoje údaje, alebo kliknite na ikonu pre prihlásenie:

WordPress.com Logo

Na komentovanie používate váš WordPress.com účet. Odhlásiť sa / Zmeniť )

Twitter picture

Na komentovanie používate váš Twitter účet. Odhlásiť sa / Zmeniť )

Facebook photo

Na komentovanie používate váš Facebook účet. Odhlásiť sa / Zmeniť )

Google+ photo

Na komentovanie používate váš Google+ účet. Odhlásiť sa / Zmeniť )

Connecting to %s