Laberint foradat P42000


Statement
 

Graphic problem

pdf   zip

thehtml

L’Izan està jugant a un videojoc consistent a moure uns blocs cilíndrics per un laberint. Algunes de les caselles del laberint, però, tenen un forat, i no és possible passar-hi. Ara bé, si es llença un bloc a un forat, aquest queda tapat, i llavors resulta possible passar per la casella. L’Izan comença a l’entrada del laberint amb uns quants blocs, i el seu objectiu és moure’s pel laberint, només amb moviments verticals i horitzonals, fins a dipositar un d’aquests a la sortida del laberint, que també té un forat. Com que ja és un expert en aquest joc, l’Izan s’ha proposat un repte més gran: vol arribar a la sortida usant el mínim nombre de blocs possible ‍i, en cas d’empat, escollint la manera que minimitza la distància del recorregut que faci fins a la sortida.

Entrada

L’entrada comença amb les dimensions del laberint: dos enters n i m entre 4 i 100. Segueix la descripció del laberint en n línies, cadascuna amb m caràcters. L’entrada s’indica amb una ‍‘E’, la sortida amb una ‘S’, els murs amb ‘X’, i els forats amb ‘O’. El laberint té exactament una entrada i una sortida, i totes les caselles de la vora són murs. A continuació ve el nombre de blocs c, entre 1 i 25, seguit de c línies, cadascuna amb el color d’un dels blocs, tots diferents i en l’ordre en què s’han de fer servir.

Sortida

Seguiu el format dels exemples. Cal representar cada casella amb un quadrat de costat 25. Pinteu els murs de color ‘Brown’, les caselles per les que passi l’Izan de color ‘Darkseagreen’, i la resta de caselles de color ‘White’. Els forats han de ser cercles de diàmetre 15 centrats a la casella corresponent. Si queden ocupats per algun bloc, pinteu el cercle del color d’aquest bloc, i altrament de color ‘Black’. Sempre hi haurà prou blocs per arribar a la sortida del laberint, i la solució serà sempre única.

Public test cases
  • Input

    9
    10
    XXXXXXXXXX
    X........X
    X.XXXXXX.X
    X.XXXXXXSX
    XEXXXXXX.X
    X.XXXXXX.X
    X.XXXXXX.X
    X........X
    XXXXXXXXXX
    1
    Purple
    

    Output

    sample-0.png

     (250×225)

  • Input

    5
    10
    XXXXXXXXXX
    XO...O...X
    X.XXXXXX.X
    X.S.OOOE.X
    XXXXXXXXXX
    4
    Red
    Blue
    Yellow
    Purple
    

    Output

    sample-1.png

     (250×125)

  • Input

    5
    10
    XXXXXXXXXX
    XO...O...X
    X.XXXXXXOX
    X.S.OOOE.X
    XXXXXXXXXX
    4
    Red
    Blue
    Yellow
    Purple
    

    Output

    sample-2.png

     (250×125)

  • Input

    9
    13
    XXXXXXXXXXXXX
    XEOO...OXO..X
    XOXXXXX.XXXXX
    X.X..X.OX.XXX
    X.OX...OOO.XX
    XX...X.X.O..X
    X.XXX..X.O.OX
    X..OO..O.XS.X
    XXXXXXXXXXXXX
    6
    Blue
    Green
    Coral
    Gold
    Purple
    MediumBlue
    

    Output

    sample-3.png

     (325×225)

  • Information
    Author
    Max Balsells
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python