Trampas para Gatos
Un número de gatos callejeros andan sueltos en la capital del azúcar, y como Recogedor de Gatos de la Ciudad, a usted se le ha asignado la tarea de atraparlos a todos. Esta es una oportunidad ideal para probar su última invención, una trampa para gatos la cual le garantizará atrapar a cada gato que camine por dentro de una subdivisión de la ciudad en forma cuadrada.
Afortunadamente, usted tiene la colaboración de uno de los gatos psicólogos más famosos del mundo, quien tiene la asombrosa habilidad de predecir, dada una subdivisión cuadrada de la ciudad, exactamente a cuál de las cuatro direcciones cardinales (norte, este, sur u oeste) el gato se dirigirá. Mientras esta información es conveniente, usted sin embargo no sabe dónde están actualmente todos los gatos.
Para probar la rentabilidad que su método tendrá para la ciudad, por supuesto, escriba el programa herding para minimizar el número de trampas usadas.
Entrada
La entrada comenzará con una línea consistente de dos números y , separados por un espacio . La ciudad será una grilla de \(n×m\) subdivisiones cuadradas. Las próximas líneas consistirá cada una de una cadena de longitud , consistente de las letras \(‘N’, ‘E’, ‘S’\), o \(‘W’\), representando norte, este, sur y oeste respectivamente. El primer caracter de la primera línea será el punto más noroeste. La dirección en el cuadrado es la dirección a la cual los gatos se dirigirán si ellos están en ese cuadrado. El gato psicólogo asegura que los gatos no tienen interés en irse de la ciudad.
Salida
El número mínimo de trampas necesarias.
Ejemplo de Entrada
3 4
SWWW
SEWN
EEEN
Ejemplo de Salida
2
Comments