Importància de les caselles P24979


Statement
 

Graphic problem

pdf   zip

thehtml

Considereu un tauler n × m amb obstacles. S’ha d’anar des d’una casella inicial fins a una casella final, fent moviments horitzontals i verticals, mai sortint fora del tauler, i mai passant per cap obstacle. A més, cal fer el mínim nombre de moviments possible.

En general, hi haurà més d’un camí mínim que compleixi les restriccions. Per a cada casella (x, y) del tauler, definim la seva importància Ixy com el nombre de camins mínims que passen per (x, y). El vostre programa haurà de pintar cada casella amb una intensitat de vermell proporcional a la seva importància.

Entrada

L’entrada comença amb una línia amb n i m, ambdues entre 1 i 100. Segueixen n línies amb m ‍caràcters cadascuna. Els obstacles es marquen amb asteriscs, les caselles lliures amb punts, la casella inicial amb una ‘I’, i la casella final amb una ‘F’. Sempre hi haurà exactament un inici i un final, i sempre es podrà arribar al final des de l’inici.

Sortida

Genereu una imatge (10m × 10n) amb un quadrat 10 × 10 per a cada casella. Pinteu cada obstacle amb el color ‘Blue’. Pinteu cada casella lliure per la qual no passa cap camí mínim amb el color ‘Green’.

Sigui M la màxima Ixy. Amb els jocs de prova donats, sempre es complirà M ≤ 255. Sigui k = 255//M. Pinteu les caselles (x, y) per les quals passen Ixy > 0 camins mínims amb el color (k*Ixy, 0, 0).

Considereu el primer exemple d’entrada. Per la casella inicial passen (surten) 7 camins mínims. Així doncs, tenim M = 7 i k = 36. La casella central del tauler s’ha pintat de color (36*4, 0, 0) = (144, 0, 0), perquè hi passen 4 camins mínims.

Puntuació

  • Cas A:  ‍40% Punts ‍

    Casos on hi ha exactament un camí mínim, com l’exemple d’entrada 2.

  • Cas B:  ‍60% Punts ‍

    Resta de casos.

Public test cases
  • Input

    3 7
    .I.*...
    ......*
    *...F..
    

    Output

    a-sample-1.png

     (70×30)

  • Input

    1 10
    *F....I.*.
    

    Output

    ab-sample-2.png

     (100×10)

  • Input

    10 18
    ..................
    .************.***.
    .*..........*...*.
    F*...........**...
    *..............**.
    ................*.
    ................*.
    ................*.
    ................*.
    .................I
    

    Output

    az-sample-3.png

     (180×100)

  • Input

    6 6
    .....I
    ......
    ......
    ......
    ......
    F.....
    

    Output

    az-sample-4.png

     (60×60)

  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python