Pixel art P38156


Statement
 

Graphic problem

pdf   zip

thehtml

En Max ha fet un programa per dibuixar. En obrir l’aplicació, apareix una graella amb m × n píxels en blanc. A continuació, es poden clicar els píxels d’un en un.

Com que aquest procediment és poc eficient, s’ha afegit una funcionalitat: si s’acaba de pintar el píxel (x, y), aleshores també es pot pintar el píxel (x+1, y), (x−1, y), (x, y−1) o (x, y+1), i així successivament, passant si cal sobre caselles ja pintades, però mai sortint fora de la graella.

Donat el dibuix que voldria pintar en Max, trobeu quin és el màxim nombre de píxels que podrà pintar si només pot clicar k píxels inicials.

Entrada

Les dues primeres línies contenen el color de fons i el color del dibuix. Les tres línies següents contenen n, m i k. A continuació venen n línies, cadascuna amb m caràcters: punts per píxels en blanc, i ‘X’s per píxels que es voldrien pintar. Podeu suposar n, m ≥ 1 i k ≥ 0.

Sortida

Dibuixeu la imatge que tingui el màxim nombre de píxels pintats, clicant com a molt k píxels inicials, i no pintant cap dels píxels en blanc. Amb els jocs de proves donats, la solució serà única.

Public test cases
  • Input

    Cyan
    Magenta
    10
    12
    4
    .X........XX
    ..XXX..XXX.X
    ...X....X...
    .....XX.....
    ..X..XX.XX..
    ............
    ..XX....XX..
    ...XX..XX.X.
    ..X.XXXX..X.
    ..XX......X.
    

    Output

    sample-1.png

     (12×10)

  • Input

    Beige
    Red
    1
    9
    1
    .XX.XXX.X
    

    Output

    sample-2.png

     (9×1)

  • Input

    LightBlue
    DarkBlue
    10
    10
    100
    X........X
    .XXX..XXX.
    ..........
    XXXXXXXXXX
    X........X
    X.XXX..X.X
    X.X.X.X..X
    X.XXX..X.X
    X........X
    XXXXXXXXXX
    

    Output

    sample-3.png

     (10×10)

  • Information
    Author
    Edgar Moreno
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python