En Johnny i en Roy no van a classe; prefereixen jugar a guerres de barcos. Com ara volen jugar-hi amb ordinador, han demanat a l’Steffy que els en faci un programa. Malauradament, l’Steffy està estudiant problemes NP-complets, així que us ha passat l’encàrrec a vosaltres.
Amb les regles d’en Johnny i en Roy, el joc es juga en una graella rectangular. Primer, en Johnny col·loca els vaixells d’amagat d’en Roy. Després, en Roy dispara trets, intentant enfonsar els vaixells. Quan a la coordenada on dispara en Roy no hi ha cap vaixell, en Jonny diu “aigua”. Quan un vaixell és tocat però no enfonsat, en Johnny diu “tocat”. Quan l’últim tret fa que totes les posicions d’un vaixell hagin estat tocades, en Johnny diu “enfonsat”, però a partir d’aquest moment dirà “aigua” per a qualsevol d’aquestes posicions.
Feu un programa que llegeixi una graella de vaixells i una seqüència de trets. Per a cada tret, el programa ha de dir “aigua”, “tocat” o “enfonsat” segons les regles. A més, el programa ha de mostrar l’estat final de la flota.
Entrada
Primer es donen el nombre de files f i el nombre de columnes c de la graella; es compleix 3 ≤ f ≤ 26 i c ≥ 3. A continuació venen f línies amb c caràcters cadascuna. Un punt indica una posició buida, una ‘V’ una posició d’un vaixell. Els vaixells es troben col·locats horitzontalment, i no es toquen entre ells ni toquen els marges de la graella. Finalment es dóna una seqüència no buida de trets (tots dins de la graella), indicant la fila amb una lletra minúscula i la columna amb un natural. La posició de dalt a l’esquerra és la a0.
Sortida
Cal escriure cada tret seguit del seu resultat (“aigua”, “tocat” o “enfonsat”) segons es mostra als exemples. A continuació, cal escriure una línia en blanc, i després mostrar l’estat final de la graella. Escriviu un caràcter ‘T’ per a les posicions tocades pero no enfonsades.
Input
5 12 ............ ..VV...V.... ............ .V.....VVVV. ............ a0 e11 b3 b3 b2 b3 b2 d1 d1 d10 d8
Output
a0: aigua e11: aigua b3: tocat b3: tocat b2: enfonsat b3: aigua b2: aigua d1: enfonsat d1: aigua d10: tocat d8: tocat ............ .......V.... ............ .......VTVT. ............
Input
6 8 ........ .VVVV.V. ........ .VVV.... .....VV. ........ b1 b2 b4 d3 d2 b6 e5 b1 d2 e5
Output
b1: tocat b2: tocat b4: tocat d3: tocat d2: tocat b6: enfonsat e5: tocat b1: tocat d2: tocat e5: tocat ........ .TTVT... ........ .VTT.... .....TV. ........
Input
3 3 ... ... ... b2
Output
b2: aigua ... ... ...