Laberint foradat P42000

Graphic problem

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.