Informatika gyűjtemény

Egy szinttel feljebb Vidampark.cs

2004050607080910

<<  12. óra  >>

<<  Vidámpark  >>

NézetNyomtat

Vidampark.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 3 KB
/*
 * Vidámpark (http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0809/12ora/vidampark)
 * Írta: Kriván Bálint, Fehér Gábor javaslata alapján (2008. 12. 11)
 * 
 * Röviden az algoritmus:
 * - Egy N*K igaz/hamis tömbben tároljuk, hogy az i-ik  szobában a j-ik jegyfizetésnél lehet-e lenni.
 * - Nyilván akkor van megoldás, ha az N-ik (utolsó) szobában a K-ik jegyvásárlásnál lehetünk.
 * - Közben eltároljuk az "apa pointereket" is, hogy egy lehetséges bejárást is adhassunk.
 */
 
using System;
using System.IO;
using System.Collections.Generic;

namespace Vidampark
{
    class Vidampark
    {
        private byte n,k;
        private int m;
        
        // az i. szobában vehetjük-e a j. jegyet.
        private bool[,] canBeHere;
        private byte[,] previousRoom;
        
        // melyik szoba után melyik szobába mehetünk
        private List<byte>[] nextRooms;
        
        private string endingFilenamePart;
        
        public Vidampark( string endingFilenamePart )
        {
            this.endingFilenamePart = endingFilenamePart;
            StreamReader ins = new StreamReader("vidam.be"+this.endingFilenamePart);
            string[] line = ins.ReadLine().Split(' ');
            n = Byte.Parse(line[0]);
            m = Int32.Parse(line[1]);
            k = Byte.Parse(line[2]);
            
            canBeHere = new bool[n,k];
            previousRoom = new byte[n,k];
            for( int i=0; i<n; i++ ) {
                for( int j=0; j<k; j++ ) {
                    canBeHere[i,j] = false;
                }
            }
            canBeHere[0,0] = true;
            
            nextRooms = new List<byte>[n];
            int a, b;
            for( int i=0; i<m; i++ ) {
                line = ins.ReadLine().Split(' ');
                a = Int32.Parse(line[0])-1;
                b = Int32.Parse(line[1])-1;
                if( nextRooms[a] == null ) nextRooms[a] = new List<byte>();
                nextRooms[a].Add((byte)b);
            }
            
            doSomeMagic();
        }
        
        private void doSomeMagic() {
            StreamWriter outs = new StreamWriter("vidam.ki"+this.endingFilenamePart);
            // megnézzük, hogy a második jegyet hol használhatjuk
            for( int i=1; i<k; i++ ) { // 1-től indulunk!!!
                for( int j=0; j<n; j++ ) {
                    // végignézzük az összes eddigi szobát, és megvizsgáljuk, hogy az előző jegyet, melyik teremben használhattuk
                    if( canBeHere[j,i-1] ) {
                        // ha az előző jegyet a j. szobában használhattuk, akkor a mostanit használhatjuk a j-ből elérhető szobákban
                        if( nextRooms[j] != null ) {
                            foreach( byte nextRoom in nextRooms[j] ) {
                                // jelöljük be, hogy elérhető a mostani jegyel a j-ből elérhető szovák
                                canBeHere[nextRoom, i] = true;
                                // jegyezzük meg, hogy a i. jegy elhasználásánál melyik szobából érkezhettünk.
                                previousRoom[nextRoom, i] = (byte)j;
                            }
                        }
                    }
                }
            }
            
            if( !canBeHere[n-1, k-1] ) {
                // ha nem lehet k jegyel eljutni az utolsó terembe
                outs.WriteLine(0);
            } else {
                // ha el lehet, akkor keressünk vissza egy lehetséges útvonalat.
                byte[] way = new byte[k];
                way[k-1] = (byte)(n-1); // a célállomás ismert, hiszen ez az utolsó terem
                for( int i=k-1; i>0; i-- ) {
                    way[i-1] = previousRoom[way[i], i];
                }
                for( int i=0; i<k; i++ ) {
                    if( i!=0 ) outs.Write(" ");
                    outs.Write((way[i]+1));
                }
                // visszakövetjük.
            }
            //Console.ReadKey();
            outs.Close();
        }
        
        public static void Main(string[] args)
        {
            // az összes tesztesetre lefuttatjuk
            new Vidampark(""); // 0. teszteset - honlapon fent lévő
            // többi a zipből származó
            new Vidampark("1");
            new Vidampark("2");
            new Vidampark("3");
            new Vidampark("4");
            new Vidampark("5");
            new Vidampark("6");
            new Vidampark("7");
            new Vidampark("8");
            new Vidampark("9");
        }
    }
}
(Vissza)