Robots Limpiadores P88988

En la nueva terminal del aeropuerto de Robotilandia acaban de estrenar un moderno sistema de limpieza del suelo mediante robots autónomos. El suelo del aeropuerto está dividido en baldosas cuadradas de un metro de lado. Inicialmente, los robots están escondidos bajo algunas de las baldosas; cuando los robots se ponen en marcha, salen de su escondite y, en función de su programación, se mueven horizontal o verticalmente un determinado número de baldosas, dan media vuelta y regresan a su escondite, limpiando todas aquellas baldosas por las que pasan, incluyendo la suya propia. Cada baldosa sólo puede ocultar un robot limpiador.

El único problema del sistema es su precio, ya que los robots son muy caros. Por ello se quiere minimizar el número de robots usados para limpiar todo el aeropuerto. Además, se requiere que ninguna casilla sea limpiada por dos robots diferentes, ya que esto desgastaría demasiado el suelo. Tu tarea es calcular el mínimo número de robots necesarios para limpiar el suelo a partir del mapa de las salas del aeropuerto.

Entrada

En la primera línea se especifica el número de casos de prueba a solucionar. En la primera línea de cada caso se especifica el tipo de robots disponibles, ya que a veces nos interesará usar solamente robots que se muevan en una dirección determinada. La palabra ‘H’ indicará que sólo se pueden usar robots que se muevan en horizontal, la palabra ‘V’ indica que sólo se pueden usar robots que se muevan en vertical, y la palabra ‘HV’ indica que pueden moverse en ambas direcciones. A continuación, una línea con el número de filas $n$ y de columnas $m$ del mapa, seguida de $n$ líneas con $m$ caracteres: un carácter ‘.’ indica una casilla a limpiar, mientras que un carácter ‘X’ indica que la casilla está ocupada por algún obstáculo, y por lo tanto no debe ser limpiada. Los robots no pueden atravesar las casillas con ‘X’.

Dispones de un segundo de CPU por cada caso que tengas que resolver.

Salida

Una línea por caso, con el número de robots necesarios para limpiar la sala del aeropuerto.

Puntuación

• Test1:

  Resolver una entrada con 10 casos con ninguna casilla del tipo ‘X’ y con $n, m \leq 100$.

• Test2:

  Resolver una entrada con 10 casos con sólo una dirección disponible y $n, m\leq 100$.

• Test3:

  Resolver una entrada con 10 casos con las dos direcciones disponibles y $n,m\leq 4$.

• Test4:

  Resolver una entrada con 10 casos con las dos direcciones disponibles y $n\leq 8$ y $m\leq 40$ (hay salas del aeropuerto que son muy alargadas).