Reinos P42782


Statement
 

pdf   zip

thehtml

“¡Que cada siervo pague sus impuestos a la capital del reino que le quede más cerca!”. Y dicho esto, los como mucho 26 nobles del reino se besaron mutuamente en la boca y firmaron una paz firme y durarera. La mayoría de siervos tampoco tenían motivo para quejarse: no tendrán que moverse demasiado para pagar los impuestos.

Se te pide que hagas un programa que, a partir del mapa del reino, calcule cuantas monedas de oro cobrará cada noble, sabiendo que:

  • Los siervos se mueven horizontal y verticalmente (pero no en diagonal).
  • Las casillas con letras A-Z (como mucho una por cada letra) contienen las capitales del reino.
  • Las casillas con punto . son casillas transitables.
  • Las casillas con un símbolo # son casillas con agua: los siervos no pueden avanzar por ellas.

Entrada

Una número arbitrario de casos. Cada caso empieza con una línea con dos enteros f y c, seguido de f filas de c caracteres cada una con la descripción del mapa (caracteres A-Z,.,#, y de una línea con 3 guiones.

Salida

Para cada caso, escribe el mapa, usando letras mayúsculas para indicar a qué reino deberá pagar impuestos un siervo que viviera en una de las casillas transitables. Escribe un asterisco (*) en aquellas casillas en las que los siervos deberían pagar impuestos a más de una capital. No modifiques las casillas que corresponden a siervos que no pagan impuestos (porque no puede llegar a ninguna capital) o las casillas con agua.

Escribe una línea con tres guiones al final de la salida de cada caso de pruebas.

Puntuación

  • TestA:  ‍20 Puntos ‍

    Entradas donde f,c≤ 10, donde siempre hay únicamente dos reinos A y B, y donde no hay casillas con agua, como en el Ejemplo ‍1.

  • TestB:  ‍20 Puntos ‍

    Entradas donde f,c≤ 50, donde hay cualquier cantidad de reinos, y donde no hay casillas con agua, como en el Ejemplo ‍2.

  • TestC:  ‍30 Puntos ‍

    Entradas donde f,c≤ 50 de cualquier tipo, como en el Ejemplo ‍3.

  • TestD:  ‍30 Puntos ‍

    Entradas donde f,c≤ 500 de cualquier tipo.

Public test cases
  • Input

    4 4
    ...B
    ....
    ....
    A...
    ---
    4 4
    A...
    ....
    ....
    ...B
    ---
    4 4
    A...
    ....
    ..B.
    ....
    ---
    3 4
    .AB.
    ....
    ....
    ---
    6 6
    .A....
    ......
    ...B..
    ......
    ......
    ......
    ---
    

    Output

    *BBB
    A*BB
    AA*B
    AAA*
    ---
    AAA*
    AA*B
    A*BB
    *BBB
    ---
    AA**
    A*BB
    *BBB
    *BBB
    ---
    AABB
    AABB
    AABB
    ---
    AAA***
    AA*BBB
    **BBBB
    **BBBB
    **BBBB
    **BBBB
    ---
    
  • Input

    2 7
    .BC.EF.
    .......
    ---
    5 6
    ...I..
    .Z....
    .....K
    ......
    ......
    ---
    6 8
    AB...I..
    CZ......
    ........
    .......K
    ........
    ..L.....
    ---
    3 5
    .....
    .....
    .....
    ---
    

    Output

    BBC*EFF
    BBC*EFF
    ---
    ZZIII*
    ZZZI*K
    ZZZ*KK
    ZZZ*KK
    ZZZ*KK
    ---
    ABB*IIII
    CZZZIIIK
    CZZZIIKK
    CZLLKKKK
    *LLLLKKK
    LLLLLLKK
    ---
    .....
    .....
    .....
    ---
    
  • Input

    3 6
    ...I..
    .Z....
    .....K
    ---
    5 8
    AB#..I..
    CZ#.....
    ..#....K
    ....####
    ..L.#...
    ---
    3 6
    ..A.B.
    ###.##
    ......
    ---

    Output

    ZZIII*
    ZZZI*K
    ZZZ*KK
    ---
    AB#IIII*
    CZ#III*K
    CZ#L**KK
    C*LL####
    LLLL#...
    ---
    AAA*BB
    ###*##
    ******
    ---
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++