El problema de ``el Joc'' P56892

Aquí, haureu de resoldre un problema que és útil per a molts “Jocs” d’Algorísmia (i d’EDA): Donat un tauler n × m amb tresors i obstacles, cal calcular la distància de cada posició del tauler al tresor més proper. Suposeu que els moviments permesos només són horitzontals i verticals, i que no es pot passar per cap obstacle ni sortir del tauler.

Entrada

L’entrada consisteix en diversos casos, cadascun amb les mides n i m, seguides d’n línies amb m caràcters cadascuna: els punts indiquen posicions lliures, les ‘T’ tresors, i les ‘X’ obstacles. Suposeu 1 ≤ n · m ≤ 10⁶.

Sortida

Per a cada cas, i per a cada posició, si conté un obstacle, marqueu-ho amb un -2. Altrament, escriviu la distància mínima a un tresor, o un -1 si no se’n pot arribar a cap. Escriviu una línia amb 10 guions al final de cada cas.