Centre comercial

(Us recomanem resoldre aquest problema en C++.)

Demà serà l’aniversari de la Gisela, i l’Emma encara no li ha comprat
cap regal. Desesperada, obté el plànol de les plantes del centre
comercial més proper, les quals estan connectades amb diversos ascensors
bidireccionals. L’Emma té poc temps (com n’és, de despistada!), així que
només podrà anar a una sola botiga x, que escollirà segons dos
paràmetres: la distància d_(x) que hagi de recórrer per arribar-hi, i
l’afinitat a_(x) de la botiga amb el regal que té pensat comprar. Si
definim v_(x) com el quocient (real) a_(x)/d_(x), l’Emma vol escollir la
botiga x amb el màxim v_(x). La podeu ajudar?

Observacions: No cal tenir en compte el camí de tornada. El camí cap a
una botiga no pot passar per altres botigues ni per obstacles, però sí
que pot travessar el trajecte dels ascensors, ja siguin les caselles
inicial, final o intermèdies. L’Emma es troba inicialment a l’extrem
superior esquerre (la casella (0, 0)) de la planta 0. Dintre de cada
planta, només es pot moure horitzontalment o verticalment, sense sortir
mai del centre comercial. Cada ascensor només connecta les dues plantes
dels extrems (no pot fer parades intermèdies). Cada trajecte complet
d’un ascensor i cada pas entre dues caselles adjacents d’una planta
costa 1.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre
de plantes n, el nombre de botigues m, i l’amplada a i la llargada ℓ de
les plantes del centre comercial. Després venen les n plantes 0, …,
n − 1, cadascuna amb a línies amb ℓ caràcters. Finalment, venen m enters
positius a_(i) indicant l’afinitat de la botiga representada per la
lletra i-èsima de l’alfabet anglès. Suposeu 1 ≤ n ≤ 10, 2 ≤ m ≤ 26, que
a i ℓ es troben entre 2 i 100, i 1 ≤ a_(i) ≤ 10⁴.

Al plànol de cada planta, els ‘#’ indiquen obstacles, els punts indiquen
caselles lliures, les primeres m lletres majúscules indiquen botigues, i
els dígits indiquen ascensors (la planta de destinació). Des de
l’entrada, que sempre estarà lliure, es pot arribar a totes les
botigues.

Sortida

Per a cada cas, escriviu la lletra de la botiga òptima, així com la
distància que cal recórrer per arribar-hi. Amb els casos donats no hi
haurà empats.

Informació del problema

Autoria: Àlex Touza

Generació: 2026-02-28T13:57:28.556Z

© Jutge.org, 2006–2026.
https://jutge.org
