Importància de les caselles P24979

Considereu un tauler $n \times 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 \times 10n)$ amb un quadrat $10 \times 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 \le 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:

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

• Cas B:

  Resta de casos.