Centre comercial P10567

(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 $\ell$ de les plantes del centre comercial. Després venen les $n$ plantes 0, …, $n - 1$, cadascuna amb $a$ línies amb $\ell$ 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 \le n \le 10$, $2 \le m \le 26$, que $a$ i $\ell$ es troben entre 2 i 100, i $1 \le a_i \le 10^4$.

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.