Guerra de plataformes P22632


Statement
 

pdf   zip

thehtml

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 ≤ xf, i 1 ≤ yc.

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).

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++