Pot po papirju

Pot po papirju

Avtor: Andrej Pavšič

Navodilo naloge

Polžek Pepe potuje po papirju. Pot prične v točki (0,0) in nadaljuje v skladu z navodili, zapisanimi v nizu znakov, sestavljenih iz črk L (ki pomeni pomik za eno enoto v levo), R (desno), U (gor) in D (dol) in morebitnimi števili (od 1 do 9), ki pomenijo, da se prejšnji pomik tolikokrat izvede. Izračunaj končno točko te poti. Če pot vsebuje cikle, izpiši navodila, ki ga vodijo po isti poti, a brez nepotrebnih ciklov.

Niz navodil: LU2LDR3
Pepe bo prišel v točko (1,1).
Krajša pot je: LURR.


Rešitev naloge predstavi tudi grafično. Nariši celoštevilsko mrežo (tj. minimalni pravokotnik), ki obsega celotno pot v svoji notranjosti. Celotno pot in krajšo pot predstavi v različnih barvah.

Opis problema in ideja rešitve

Spremljati moramo potovanje polžkovo gibanje po točkah, ki jih prehodi. Za določanje točke bomo potrebovali dve koordinati, ker se polžek giblje po dvodimenzionalnem prostoru. Ker je potrebno tudi vrniti morebitno krajšo, je smiselno vse prehojene točke, ki jih določa niz navodil, shraniti v tabelo poti. Iz te tabele je potem hitro razvidno, če se polžek kje zacikla oz. če se katera točka v nizu nahaja več kot enkrat.

  • Končno točko lahko odčitamo iz tabele poti – to je točka, ki se nahaja na zadnjem mestu v tej tabeli.

  • Krajšo pot določimo tako, da iz potovanja polžka izločimo vse nepotrebne cikle, ki jih polžek naredi. Cikel lahko v tabeli poti vidimo, če se v tabeli nahajata isti točki – če polžek pride na točko, na kateri se je pred tem že nahajal, je pot od prve pojavitve točke dalje do vključno trenutne točke odvečna.
    Krajšo pot bomo dobili s pomočjo označevanja točk. Ustvarili bomo novo tabelo tipa int[], enake dolžine kot je tabela poti, kjer bomo vsaki točki na vzporedno mesto nove tabele (na mesto z istim indeksom) shranili oznako.
    Polžkovo pot bomo pričeli z oznako 1 – to oznako sprva dodelimo izhodišču, ki se nahaja na začetku tabele. Spustimo zanko po tabeli poti, oznake pa točkam pripisujemo takole:

    • v primeru, da polžek še ni šel čez trenutno točko, oznako samo shranimo v tabelo oznak na vzporedno mesto, oznako pa povečamo za 1;
    • v primeru, da je polžek že bil na trenutni točki, oznako shranimo (oz. spremenimo) prvi pojavitvi te točke in oznako povečamo za 1 (trenutni točki ne pripišemo oznake).
  • Ko dobimo tabelo oznak, nas v njej zanimajo samo naraščajoče oznake. Če neki točki neposredno sledi točka z manjšo oznako, je ta točka začetek cikla. Prva točka izven cikla ima večjo oznako kot jo ima točka pred ciklom. S še eno zanko pa lahko vrnemo niz okrajšane poti. Zanko spustimo po tabeli oznak od drugega elementa dalje (prvi element v tabeli je izhodišče, tu pa ni premika), kjer pri ustreznih oznakah točk v niz okrajšane poti dodamo ustrezen premik.

Grafično bomo pot in krajšo pot lahko prikazali s pomočjo tabele točk poti in table točk krajše poti. Pot pričnemo izrisovati iz sredine risalne površine – x koordinato dobimo z polovico dolžine površine, y pa z polovico višine platna. Ker imamo v obeh tabelah shranjene premike za ena (v katerokoli smer) oz. celoštevilske premike po koordinatnem sistemu, lahko pri izrisu to s pridom uporabimo. Odmik od izhodišča samo pomnožimo s smiselnim koeficientom, da bo slika dobro vidna. Npr. pri koeficientu 10 bi točko (3,-1) narisali za 30 enot desno in 10 enot dol od sredine risalne površine. Podobno velja za vmesne točke med končno in začetno.

Razlaga algoritma

Konstruktorji

Za shranjevanje točk v tabelo poti potrebujemo koordinati x in y tipa int. V konstruktorju razreda Polzek bomo hranili:

  • koordinati x in y tipa int;
  • niz navodil navodilaZaPot(brez številk – ustrezne premike bomo zapisali s črkami) in niz krajše poti krajsaPot;
  • seznam tockePot tipa Point, kjer bomo hranili vse prehojene točke polža in seznam tockeKrajsaPot tipa Point, kjer bomo hranili krajšo pot, če le ta obstaja;
  • v spremenljivki maxD tipa int pa bomo hranili največji odklon od središča – rabili ga bomo pri risanju, da bomo lahko določili smiseln koeficient za razdaljo med točkami.

Prazen konstruktor

Pri klicu praznega konstruktorja imata x in y vrednost 0, maxD vrednost 1, seznama tockePot in tockeKrajsaPot pa sta prazna. Nizov navodilaZaPot in krajsaPot ne omenjamo.

Poln konstruktor

Objekta razreda Polzek s klicem polnega konstruktorja generiramo z vnosom niza navodil, ki je sestavljen iz velikih črk U, D, L in R in število od 2 do 9. X in y nastavimo na 0, maxD na 1, ustvarimo prazna seznama tockePot in tockeKrajsaPot.
Pri branju niza navodil si bomo v primeru številke pomagali še z dvema spremenljivkama. Ena spremenljivka bo tipa int, kamor bomo shranili vrednost števila, druga bo tipa char, tja pa bomo shranili črko, ki se nahaja pred to številko.
Točke bomo dodajali s pomočjo zanke po nizu navodil. Prvo točko – koordinatno izhodišče pa dodamo še pred zanko v oba seznama.

Po nizu navodil spustimo for zanko in pregledamo vsak znak v nizu. Najprej bomo določili število premikov in to shranili v spremenljivko st, nato pa še smer premika, ki jo bomo shranili v spremenljivko trenutni.

  • Če je znak ustrezna črka, potem števec st dobi vrednost 1, smer premika pa je določena z znakom.
  • Če je znak ustrezna številka, potem števec st dobi vrednost za eno manjše od številke na i-tem koraku zanke (en premik smo namreč naredili v prejšnjem koraku zanke). Smer premika določa črka na predhodnem znaku tekočega števila.

Nato znotraj for zanke ustvarimo še eno while zanko, ki teče dokler je števec st večji od 0.

  • znak U – povečujemo y;
  • znak D – zmanjšujemo y;
  • znak L – zmanjšujemo x;
  • znak D –povečujemo x.

V niz navodilaZaPot dodajamo ustrezne črke – pridelujemo niz navodil, v katerem bomo vse številke nadomestili z ustreznim številom črk. V vsakem koraku te while zanke moramo v seznam točk, ki opisujejo pot dodati tekočo točko, ki je opisana s parom koordinat (x,y). Preveriti moramo še odmik od izhodišča – tega bomo potrebovali pri risanju polžkove poti.

Objekt razreda Polžek tako po »obdelavi« vhodnega niza hrani koordinati x in y, s ki lahko opišeta končno lokacijo polžka; niz navodil za pot (brez številk, samo črke); prazen niz krajsaPot; seznam tockePot, v katerih so hranjene vse prehojene točke; seznam tockeKrajsaPot, v katerem je samo točka (0,0); maxD pa nam opiše največji odmik od izhodišča tekom potovanja.

Končna točka

Z metodo public string Tocka() vrnemo končno točko polžka tako, da vrnemo zadnji element tabele poti.

Krajša pot

Z metodo public string KrajsaPot() vrnemo okrajšan niz navodil. V metodi najprej definiramo prazno tabelo tipa int[], kamor bomo shranjevali oznake točk in oznako tipa int z začetno vrednostjo 1. Dolžina tabele oznak je enaka dolžini tabele poti, saj vsaki točki na vzporednem mestu v tabeli oznak priredimo število. Ustvarimo tudi seznam naPoti tipa Point, v katerem bomo hranili vse točke do tekoče – to bomo potrebovali pri preverjanju, če je polžek že kdaj bil na točki, na kateri se trenutno nahaja (zato nas bodoče točke ne zanimajo).

  • S for zanko bomo pregledali vsako točko iz tabele poti. Najprej v zanki v pomožno tabelo dodamo na konec seznama tekočo točko iz tabele poti.

  • Če se točka na j-tem mestu tabele poti v pomožni tabeli nahaja več kot enkrat, lahko hitro ugotovimo s pomočjo metode Array.IndexOf(element iz seznama), ki nam vrne indeks prve pojavitve elementa iz tabele. Če je dobljeni indeks manjši od j-ja, potem imamo cikel. Oznako v tabeli oznak spremenimo na mestu, ki ga v zanki določa indeks ind:

    • če ind==j: potem spremenimo oznako v tabeli oznak na j-tem mestu;
    • če ind<j: spremenimo oznako v tabeli oznak na mestu ind, oznaka na mestu j ostane 0.
  • V zanki na koncu povečamo vrednost oznake za 1.

Po izteku zanke smo dobili tabelo oznak iz katere pa zelo preprosto dobimo krajšo pot brez ciklov. Niz krajsaPot določimo kot prazen niz, kamor bomo hranili ustrezne premike. Oznaki pa spremenimo vrednost oznake, ki pripada koordinatnemu izhodišču (pregled bomo vršili od začetka). Nato ustvarimo for zanko, v kateri pregledamo vse oznake v tabeli oznak.

  • Zanimajo nas samo oznake točk, ki so večje od vrednosti, ki jo hranimo v števcu oznaka. Če naletimo na oznako točke, ki je višja od trenutne oznake, potem nizu krajše poti dodamo znak, ki se nahaja na (k-1)-tem mestu navodil (dolžina niza navodil je za 1 manjša od dolžine tabele oznak točk, saj v tabeli točk na začetku hranimo tudi izhodišče), oznaki pa nastavimo vrednost na oznako trenutne točke.

  • Po izteku zanke samo še uredimo, kaj nam metoda vrne:

    • če je niz krajše poti enak nizu navodil, potem krajša pot ne obstaja;
    • če se polžek ustavi v točki (0,0), je njegova celotna pot en sam cikel;
    • sicer vrnemo niz krajše poti.
  • Na primeru to zgleda takole: LUULDRRR nam po izteku prve for zanke ustvari tabelo oznak [1, 2, 7, 4, 5, 6, 0, 8, 9]. Prvi element tabele pripada izhodišču (označen z modro), druga for zanka teče od drugega elementa dalje. Z rdečo so označene točke, ki nastopajo v ciklu in nas ne zanimajo. Če niz navodil LUULDRRR »okrajšamo«, dobimo LURR.

Grafični prikaz poti

Za pregleden grafični vmesnik so na formi ustvarjeni:

  • vnosno polje ob oznaki niz navodil, v katerega vnašamo polžkovo pot;
  • pod to vrstico je oznaka, ki nam izpiše, v katero točko bo polžek prišel;
  • še niže pa se izpiše polžkova krajša pot;
  • gumb, s katerim izvršimo kreacijo objekta razreda Polžek in klic metod za izračun krajše poti, končne točke in risanje poti;
  • desno od tekstovnih vsebin pa se nahaja še risalna površina.

Celotna forma hrani spremenljivke:

  • int xP, yP – x in y koordinati središča platna;
  • int premikX, premikY – velikost premika (sorazmerna velikosti risalne površine)
  • public Polzek Pepe – objekt razreda Polzek
  • int thread – v tej spremenljivki hranimo zamik v milisekundah, ki ga bomo uporabili za nazornejši prikaz premikanja polžka.

Ker nekaj istih izračunov potrebujemo večkrat in to hkrati, jih združimo v metodi Init(). Ta metoda se uporablja pri zgoraj omenjenih dogodkih, izračuna pa nam središčni koordinati risalne površine in sliko »osveži« oz. razveljavi, paint event pa jo ponovno izriše.

Na vrhu je v programu spisan še dogodek za klik z miško na vnosno polje - tbNavodila_MouseClick. Ta ima le lepotno funkcijo, saj ob kliku pobriše vnosno polje in skrije podatke o končni točki in krajši poti.

Pri grafičnem delu so pomembnejši dogodki:

  • Form1_Load (ob zagonu okna):

    • ob zagonu okna kličemo prazen konstruktor (saj nam sicer probleme predstavlja kasneje opisan dogodek za risanje) in metodo Init

  • Form1_SizeChanged (ob spreminjanju velikosti okna):

    • klic metode Init, saj je potreben izračun novega središča risalne plošče in nastavitev »zamrznitve« thread na 0, saj bi se nam sicer celotna pot ponovno izrisovala nekaj časa

  • button1_Click (ob kliku na gumb »Na pot!«):

    • nastavitev zamrznitve na 1000 ms,
    • klic polnega konstruktorja, niz je enak nizu v vnosnemu polju,
    • klic metode Init – brez invalidate ne gre
    • izračun in izpis končne točke s klicem objektne metode Tocka()
    • izračun in izpis krajše poti s klicem objektne metode VrniKrajsoPot()

  • pnlPot_Paint (risalni dogodek za risalno ploščo): za poenostavitev risanja povezav ustvarimo še seznam Pot tipa Point, kjer bomo imeli shranjene točke, ki se bodo nato risale na platno. Povezave bomo narisali kot daljice med točkami.

    • najprej pogledamo kakšna je vrednost maxD. Če je večja kot 6, potem prilagodimo razmik med točkama.
    • Sledi izris celotne poti – objekt Polžek hrani seznam točk, v katerih se polžek premika po eno enoto na vsakem koraku. Polžek svojo pot prične v izhodišču, kar je na sliki središče platna. Za izris točke potrebujemo odmik od izhodišča pomnožen z velikostjo premika, ki smo ga določili pred zanko.
    • V vseh korakih zanke razen začetnem izrisujemo tudi povezave. Povezavo narišemo kot daljico med tekočo in predhodno točko.
    • Na koncu zanke uporabimo zamrznitev, da se slika izrisuje »po korakih«.
    • podobno izrisujemo krajšo pot, le da moramo najprej preveriti, če krajša pot sploh obstaja (če sta niza navodilaZaPot in krajsaPot različna).
    • izrisujemo manjše točke in povezave ter uporabimo drugo barvo.

Koda v C#

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Threading;

namespace PotPoPapirju
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        public int xP; // x koordinata na platnu
        public int yP; // y koordinata na platnu
        int premikX, premikY; // velikost premika - sorazmerna velikosti risalne površine
        public Polzek Pepe; // objekt, ki hrani vse atribute za prikaz poti in izris poti
        int thread; // zamrznitev med izrisovanjem točk

        /// <summary>
        /// S klikom na vnosno polje skrijemo label boxe in izpraznemo vnosno polje."
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void tbNavodila_MouseClick(object sender, MouseEventArgs e)
        {
            lblKrajsaPot.Text = "";
            lblTocka.Text = "";
            tbNavodila.Text = "";
        }

        /// <summary>
        /// Inicializator izračuna središčne koordinate in "invalidira" platno - Init() uporabimo pri zagonu programa in spreminjanju velikosti okna, pri ponovnih klikih na gumb.
        /// </summary>
        public void Init()
        {
            xP = pnlPot.Width / 2; // izračun x koordinate platna
            yP = pnlPot.Height / 2; // izračun y koordinate platna
            pnlPot.Invalidate();
        }

        /// <summary>
        /// Ob zagonu programa
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form1_Load(object sender, EventArgs e)
        {
            Pepe = new Polzek();
            lblKrajsaPot.Text = "";
            lblTocka.Text = "";
            Init();
        }

        /// <summary>
        /// Ob spreminjanju velikosti okna, spreminjamo tudi grafično predstavitev poti.
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form1_SizeChanged(object sender, EventArgs e)
        {
            Init();
            thread = 0;
        }

        #region RISANJE
        /// <summary>
        /// Klik na gumb "Na pot!"
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void button1_Click(object sender, EventArgs e)
        {
            thread = 1000;
            Pepe = new Polzek(tbNavodila.Text); // ustvarimo polžka
            Init();
            lblTocka.Text = "Pepe bo prišel v točko: " + Pepe.Tocka(); // točka
            lblKrajsaPot.Text = Pepe.VrniKrajsoPot();  // krajša pot
        }


        private void pnlPot_Paint(object sender, PaintEventArgs e)
        {
            List<Point> Pot = new List<Point>();

            // če najbolj oddaljena točka ni daleč od izhodišča, spremenimo velikost premika
            if (Pepe.maxD <= 6)
            {
                premikX = Convert.ToInt32(0.08 * xP);
                premikY = Convert.ToInt32(0.08 * yP);
            }
            else
            {
                premikX = Convert.ToInt32(xP / Pepe.maxD);
                premikY = Convert.ToInt32(yP / Pepe.maxD);
            }

            // CELOTNA POT
            if (Pepe.tockePot.Count == 0)
                return;
            for (int i = 0; i < Pepe.tockePot.Count; i++)
            {
                Point tocka = Pepe.tockePot[i];
                Pot.Add(new Point(xP + tocka.X * premikX, yP - tocka.Y * premikY));
                e.Graphics.FillEllipse(Brushes.Black, Pot[i].X - 5, Pot[i].Y - 5, 11, 11); // črn krog
                e.Graphics.FillEllipse(Brushes.White, Pot[i].X - 3, Pot[i].Y - 3, 7, 7); // bel - boljša vidljivos poti, ko hodi po ciklu

                Pen blackPen = new Pen(Color.FromArgb(255, 0, 0, 0), 3);
                if (i > 0)
                {
                    e.Graphics.DrawLine(blackPen, Pot[i - 1], Pot[i]);
                }
                Thread.Sleep(thread); // ob kliku "Napot!" je thread 1s, pri spreminjanju velikosti okna 0
            }
            // KRAJŠA POT
            if (Pepe.krajsaPot != Pepe.navodilaZaPot)
            {
                if (Pepe.tockeKrajsaPot.Count == 0)
                    return;
                List<Point> KrajsaPot = new List<Point>();
                for (int j = 0; j < Pepe.tockeKrajsaPot.Count; j++)
                {
                    Point tocka = Pepe.tockeKrajsaPot[j];
                    KrajsaPot.Add(new Point(xP + tocka.X * premikX, yP - tocka.Y * premikY));
                    e.Graphics.FillEllipse(Brushes.Red, KrajsaPot[j].X - 2, KrajsaPot[j].Y - 2, 5, 5);

                    if (j > 0)
                    {
                        e.Graphics.DrawLine(Pens.Red, KrajsaPot[j - 1], KrajsaPot[j]);
                    }
                    Thread.Sleep(thread);
                }
            }

        }
        #endregion risanje
    }

    #region razred Polzek
    public class Polzek
    {
        private int _x; // x koordinata polža
        private int _y; // y koordinata polža
        private string _navodilaZaPot;
        private string _krajsaPot;

        // properties
        public int x
        {
            get { return this._x; }
            set { this._x = value; }
        }
        public int y
        {
            get { return this._y; }
            set { this._y = value; }
        }
        public string navodilaZaPot
        {
            get { return this._navodilaZaPot; }
            set { this._navodilaZaPot = value; }
        } // potek poti brez številk - premik s številkam je pretvorjen v več črk (U2 -> UU)
        public string krajsaPot
        {
            get { return this._krajsaPot; }
            set { this._krajsaPot = value;  }
        }  // krajša pot

        public int maxD; // največji odklon od središča
        public List<Point> tockePot;
        public List<Point> tockeKrajsaPot;

        /// <summary>
        /// Prazen konstruktor
        /// </summary>
        public Polzek()
        {
            x = 0; y = 0; maxD = 1;
            tockePot = new List<Point>();
            tockeKrajsaPot = new List<Point>();
        }

        /// <summary>
        /// poln konstruktor
        /// </summary>
        /// <param name="navodila">niz navodil za pot</param>
        public Polzek(string navodila)
        {
            x = 0; y = 0; maxD = 1;
            tockePot = new List<Point>();
            tockeKrajsaPot = new List<Point>();
            char[] dobri = new char[4] { 'U', 'D', 'L', 'R' };
            int st = 0; // če imamo številko za črko, se moramo večkrat pomakniti v smeri pedhodne črke - to nam pomaga ta števec
            char trenutni;

            tockePot.Add(new Point(x, y)); // prva točka v tabeli poti je izhodišče!
            tockeKrajsaPot.Add(new Point(x, y));

            for (int i = 0; i < navodila.Length; i++)
            {
                if (dobri.Contains(navodila[i]) == true) // če je znak v nizu črka
                {
                    st = 1;
                    trenutni = navodila[i];
                }
                else if (Char.IsNumber(navodila[i]) && int.Parse(navodila[i].ToString())>0) // če je znak v nizu številka
                {
                    st = int.Parse(navodila[i].ToString()) - 1; // en pomik smo že šteli v prejšnjem koraku, zato -1
                    trenutni = navodila[i - 1]; // za črko uporabimo predhodni znak trenutne številke
                }
                else
                { throw new Exception("Napačen znak na " + i + "-tem mestu. Dovoljeni so znaki: U, D, L in R."); }

                while (st > 0)
                {
                    if (trenutni == 'U') // gor
                    {
                        y += 1;
                        navodilaZaPot += "U";
                    }
                    if (trenutni == 'D') // dol
                    {
                        y -= 1;
                        navodilaZaPot += "D";
                    }
                    if (trenutni == 'L') // levo
                    {
                        x -= 1;
                        navodilaZaPot += "L";
                    }
                    if (trenutni == 'R') // desno
                    {
                        x += 1;
                        navodilaZaPot += "R";
                    }

                    tockePot.Add(new Point(x, y)); // dodamo točko v seznam "prehojene poti"

                    int k = Math.Max(Math.Abs(x), Math.Abs(y));
                    if (k > maxD)
                        maxD = k; // maximalen "odmik" v y ali v x smeri od začetne lege - za izris
                    st -= 1;
                }
            }
        }

        /// <summary>
        /// Vrne končno točko polža.
        /// </summary>
        /// <returns></returns>
        public string Tocka()
        {
            Point t = tockePot[tockePot.Count - 1];
            return "("+t.X + "," + t.Y+")";
        }

        /// <summary>
        /// Vrne krajšo pot - pot brez nepotrebnih ciklov
        /// </summary>
        /// <returns></returns>
        public string VrniKrajsoPot()
        {
            int[] oznakaPoti = new int[tockePot.Count]; // tabela z oznakami poti - vzporedna tabeli poti (element na i- tem mestu tabele poti je točka, tabele oznakaPoti pa oznaka te točke)
            int oznaka = 1;
            List<Point> naPoti = new List<Point>();

            for (int j = 0; j < tockePot.Count; j++) // vsaki točki priredimo oznako in jo "vzporedno" shranimo v tabelo oznakaPoti
            {
                naPoti.Add(tockePot[j]); // seznam, kjer so shranjene vse točke do vključno "tekoče" točke
                int ind = naPoti.IndexOf(tockePot[j]); // V primeru, da je polž že bil na "tekoči" točki (če je ind<j), potem prvi pojavitvi te točke (na trenutno prehojeni poti) oznako povečamo na trenutno.
                oznakaPoti[ind] = oznaka;                     // Sicer (ind==j) oznako shranimo točki na vzporedno mesto v tabelo oznak.
                oznaka += 1;
            }

            krajsaPot = "";
            x = y = 0;
            oznaka = oznakaPoti[0]; // začetni indeks je oznaka izhodišča
            for (int k = 1; k < oznakaPoti.Length; k++)
            {
                if (oznaka < oznakaPoti[k]) // zanimajo nas samo točke z naraščujočimi indeksi
                {
                    char trenutni = navodilaZaPot[k-1];
                    krajsaPot += trenutni; // najprej nizu dodamo ustrezen premik

                    if (trenutni == 'U') // gor
                    {
                        y += 1;
                    }
                    if (trenutni == 'D') // dol
                    {
                        y -= 1;
                    }
                    if (trenutni == 'L') // levo
                    {
                        x -= 1;
                    }
                    if (trenutni == 'R') // desno
                    {
                        x += 1;
                    }
                    tockeKrajsaPot.Add(new Point(x, y));
                    oznaka = oznakaPoti[k];     // nato pa indeks povečamo na oznako trenutne točke
                }
            }
            if (krajsaPot == navodilaZaPot)
            { return "Krajša pot ne obstaja."; }
            else if (krajsaPot == "")
            { return "Krajša pot je, če se Pepe na pot ne odpravi."; }
            else
            { return "Krajša pot je: " + krajsaPot + "."; }
        }
    }
#endregion

}

Testni primeri

Na prvi pogled je v programu najtežje spisati morebitno krajšo pot. Do končne točke ni problem priti, saj polžka pomikamo glede na vhodni niz navodil.

Zato končno točko preverimo z enim primerom, za krajšo pot pa je smiselno preveriti, kako nam jo izračuna pri primerih, ko imamo pot s cikli, če naredimo cikel in končamo v izhodišču, če se premaknemo samo levo in nazaj desno oz. gor in nazaj dol.

Pri testiranju dobrega grafičnega izrisa pa moramo preveriti, kako nam izriše polžkovo pot, ko ta potuje daleč od izhodišča. V programu testiramo poti:

  • LU2LDR3 – primer iz navodil,
  • ULDRULDR – če naredimo krog oz. dva in končamo v izhodišču,
  • LRUD – premik in nato nazaj v predhodno točko,
  • L2U4 – če imamo pot brez ciklov,
  • L9U4L3D1R5D7 – poljubna pot, ki poteka tudi daleč od izhodišča.

Ob izpisu testnih primerov vidimo, da nam končne točke računa pravilno, da krajše poti pravilno izpiše.

0%
0%