Aterrizaje P18472

—Walker, están ahí abajo —dice Trivette.

Walker pide silencio con el dedo. Ambos están encima del tejado roto de una fábrica abandonada, donde N malvados están ocupados haciendo de las suyas. Walker está calculando el punto de la fábrica al que debería tirarse desde el tejado. En concreto, Walker quiere aterrizar en aquel punto de la fábrica tal que esté lo más cerca posible de todos los malvados, o sea, el punto tal que la suma de las distancias (incluyendo movimientos en diagonal) entre el punto y los malvados sea mínima. Por ejemplo, si los malvados (‘X’) están situados sobre el mapa del siguiente modo

entonces el punto (‘a’) está a distancia 2 de todos ellos, por lo que la suma de distancias es 2+2+2+2 = 8, mientras que el punto (‘b’) está a distancias 3, 1, 1 y 2, por lo que la suma total es 7. Walker preferiría aterrizar en el punto ‘b’ antes que en el punto ‘a’. Además del punto (‘b’), hay otros 3 puntos de aterrizaje cuya suma de distancias es 7. Se permite que Walker aterrice encima de un malvado (de hecho, uno de los 3 puntos anteriores consiste en aterrizar encima del malvado de la segunda fila).

Se te pide que ayudes a Walker encontrando la suma de distancias mínimas (en el ejemplo anterior, 7), y el número de puntos distintos con tal distancia mínima (en el ejemplo anterior, 4).

Entrada

Cada entrada contiene un único caso de pruebas, con dos números F y C (filas y columnas) con las dimensiones de la fabríca abandonada, seguidos de F líneas de C caracteres cada una, bien ‘.’ (espacio vacío) o ‘X’ (los N malvados). En todos los ejemplos los malvados han sido distribuidos al azar. Fíjate, además, que en al menos 80 de los 100 puntos del problema, hay muchos más espacios vacíos que espacios ocupados por malvados.

Salida

Escribe una línea (acabada en salto de línea) con dos números separados por un espacio: la mejor suma de distancias posible, y el número de puntos donde es posible aterrizar con tal suma de distancias.

Puntuación

• TestA:  ‍ Entradas con F,C≤ 10 y N=0.  ‍10 Puntos ‍

• TestB:  ‍ Entradas con F,C≤ 10 y N=1.  ‍10 Puntos ‍

• TestC:  ‍ Entradas con F,C≤ 50 y N≤ 50.  ‍30 Puntos ‍

• TestD:  ‍ Entradas con F,C≤ 200 y N≤ 200.  ‍20 Puntos ‍

• TestE:  ‍ Entradas con F,C≤ 1000 y N cualquiera.  ‍10 Puntos ‍