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 × 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 ≤ x ≤ f, i 1 ≤ y ≤ 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 Θ(f × c).
Input
5 10 XXXXX.XXXX X...X...XX X.X.X.X..X X...X..X.. XXXXX..X.. 1 1 5 9 5 8 3 3 1 2 4 8 1 2 1 6
Output
1 1: hit 5 9: miss 5 8: hit 3 3: hit and sunk 1 2: hit 4 8: hit and sunk 1 2: REPEATED
Input
2 6 .....X XX.... 2 1 1 6 1 2 2 2 1 1 1 2
Output
2 1: hit 1 6: hit and sunk 1 2: miss 2 2: hit and sunk VICTORY
Input
1 8 .XXXX... 1 6
Output
1 6: miss UNFINISHED
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++