Harrichu y los oasis P25237

Harrichu Jones vuelve a la carga. Como de costumbre, debe conseguir tantos tesoros (‘T’) como sea posible. Sin embargo, esta vez se encuentra en el desierto: Harrichu puede avanzar a cualquiera de las cuatro casillas vecinas, pero sólo si en su cantimplora queda al menos un trago de agua. La cantimplora tiene k tragos de capacidad, pero puede rellenarse tantas veces como sea necesario visitando cualquier casilla con un oasis (‘O’). Todas las restantes casillas son o bien desierto (‘.’), o montañas (‘#’) que Harrichu no puede cruzar. Además, la casilla donde empieza Harrichu (‘H’) contiene un oasis.

Harrichu te pide que escribas un programa que calcule cuántos tesoros puede conseguir, y cuántos oasis distintos puede visitar (al fin y al cabo, le gusta hacer turismo) con la restricción de que Harrichu no debe quedarse sin agua en una casilla que no contenga un oasis. En particular, Harrichu debe finalizar su aventura en una casilla con oasis (el inicial, o cualquier otro) donde esperará cómodamente a que lo rescaten.

Entrada

Cada entrada contiene un único caso. La primera línea de la entrada contiene, separados por espacios, el número de filas 1≤ F≤ 200 y de columnas 1≤ C≤ 200 del mapa, y la capacidad de tragos k>=2 de la cantimplora. Las F líneas siguientes contienen C caracteres cada una, con el mapa del desierto: ‘T’ (tesoro), ‘O’ (oasis), ‘.’ (desierto), ‘#’ (montaña) y ‘H’ (la posición inicial de Harrichu). Siempre existirá una única casilla ‘H’. La casilla donde empieza Harrichu contiene un oasis, y todas las casillas que contienen tesoros son casillas de desierto.

Salida

Escribe dos líneas con el número de tesoros que Harrichu puede conseguir y el número de oasis que Harrichu puede visitar (incluyendo el inicial). Con las condiciones descritas en el enunciado, siempre hay una estrategia que maximiza ambos números.

Escribe la salida exactamente como se muestra en los ejemplos (cualquier desviación, por pequeña que sea, será considerada un error). Estudia los ejemplos para asegurarte que has entendido correctamente el enunciado del problema.

Puntuación

• Test1:  ‍35 Puntos ‍

  Entradas donde 5≤ f,c ≤ 50 y k=2, y el mapa está enmarcado por casillas de montaña, como en el primer ejemplo.

• Test2:  ‍45 Puntos ‍

  Entradas donde 5≤ f,c ≤ 50 y k≥ 2, y el mapa está enmarcado por casillas de montaña, como en los ejemplos 2, 3 y 4.

• Test3:  ‍20 Puntos ‍

  Entradas de todo tipo.