Trampas para Gatos


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

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 n y m, separados por un espacio (1 \leq n, m \leq 1000). La ciudad será una grilla de \(n×m\) subdivisiones cuadradas. Las próximas n líneas consistirá cada una de una cadena de longitud m, 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

There are no comments at the moment.