Guerra de plataformes P22632

Probablement coneixeu el joc “guerra de barcos”. Aquí, haureu de jugar una partida d’un joc similar, on un dels jugadors té diverses plataformes petrolieres en una tauler $f \times c$, i l’oponent vol enfonsar-les totes amb el mínim nombre de tirades. Definim una plataforma com un component connex, suposant que les unions són horitzontals i verticals, però no diagonals. (Al primer exemple d’entrada hi ha 5 plataformes.)

Entrada

L’entrada consisteix en $f$ i $c$, seguides de $f$ files amb $c$ caràcters cadascuna. Una ‘X’ indica una posició ocupada, i un punt una posició lliure. Segueixen diversos parells $x$ $y$ indicant cada tirada (fila i columna). Suposeu que $f$ i $c$ estan entre 1 i 500, $1 \le x \le f$, i $1 \le y \le c$.

Sortida

Per a cada tirada, escriviu en anglès si és aigua o és tocat i, en aquest cas, si és enfonsat. El programa ha d’acabar quan s’enfonsen totes les plataformes, quan es repeteix alguna jugada, o si no queden més tirades, amb el missatge corresponent.

Pista

La solució esperada té cost total $\Theta(f \times c)$.