Gorriones y palomas P30733

Te disponías a tirar migas de pan a los gorriones en el patio rectangular de la escuela, pero ves de reojo que hay una buena cantidad de palomas gordas al acecho. Sabes que una vez una miga toque el suelo, se la llevará el pájaro situado más cerca de la miga (en concreto, el que necesite moverse el mínimo número de casillas, en cualquiera de las ocho direcciones, para llegar a su objetivo). Por ejemplo, si tenemos a 3 gorriones (G) y 2 palomas (P) situados en las posiciones siguientes,

y marcamos con g (respectivamente, p) aquellas casillas donde, caso de caer una miga, se la acabaría comiendo un gorrión (respectivamente, una paloma), obtendremos lo siguiente:

Los puntos son aquellas casillas en las que no está claro si la miga se la comería una paloma o un gorrión, dado que se produce un empate. En este caso, y sin importar el número de palomas o gorriones que estén a igual distancia, siempre consideraremos que hay un 50% de probabilidad que la miga se la acabe llevando un gorrión.

Tu objetivo es lanzar las migas a aquellos lugares del parque en los que serían comidas por un gorrión Sin embargo, tu puntería no es tan buena como querrías: si intentas lanzar una miga a una casilla (i, j), la miga puede caer en cualquier casilla que esté a distancia T o menos de tu casilla objetivo (i, j) (es decir, en cualquier casilla del cuadrado de lado 2T+1 centrado en (i, j)). No está permitido que lances la miga a un lugar tal que haya alguna posibilidad de que ésta caiga fuera del patio (o sea, no puedes lanzar a una casilla que esté a menos de distancia T del exterior). Te pedimos que encuentres dónde deberías intentar apuntar para maximizar las posibilidades de que la miga sea comida por un gorrión.

Entrada

Una línea con los números n y m (filas y columnas). Se cumple 2T+1 ≤ min(n, m). A continuación, n líneas de m caracteres cada una, con puntos (casilla vacía), P (paloma) o G gorrión. Por último, una cantidad arbitraria (posiblemente 0) de valores T≥ 0 (tu error máximo al apuntar), uno por línea.

Salida

Escribe el mapa que indica, para cada casilla, si llegará antes un gorrión g o una paloma p, como en el ejemplo. A continuación, y para cada valor de T, escribe una línea con dos números separados por un espacio, con la fila y la columna (empezando en 1) de la casilla donde deberías apuntar para maximizar las posibilidades de alimentar a un gorrión si tu error al apuntar es T. Si hay más de una casilla posible, escribe aquella con menor fila; si sigue habiendo más de una, escribe aquella con menor columna. Recuerda que no se consideran válidas aquellas casillas en las que es posible tirar la miga fuera del patio (por ejemplo, la primera casilla válida es la (T+1, T+1)).

Puntuación

• TestA:  ‍30 Puntos ‍

  Entradas con n, m < 20 y ningún valor de T (sólo tienes que escribir el mapa).

• TestB:  ‍ Entradas con n, m < 20 y no más de 10 valores T < 10.  ‍20 Puntos ‍

• TestC:  ‍ Entradas con n, m < 200 y no más de 10 valores T < 100.  ‍20 Puntos ‍

• TestD:  ‍ Entradas con n, m < 1000 y no más de 10 valores T < 500.  ‍30 Puntos ‍