Importància de les caselles P24979

Graphic problem

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 I_xy 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 I_xy. Amb els jocs de prova donats, sempre es complirà M ≤ 255. Sigui k = 255//M. Pinteu les caselles (x, y) per les quals passen I_xy > 0 camins mínims amb el color (k*I_xy, 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.