HERDING - Herding


Oh no! A number of stray cats have been let loose in the city, and as the City Cat Catcher, you have been assigned the vital task of retrieving all of the cats. This is an ideal opportunity to test your latest invention, a cat trap which is guaranteed to retrieve every cat which walks into a square-shaped subsection of the city.

Fortunately, you have the assistance of one of the world's foremost cat psychologists, who has the amazing ability of predicting, given a square subsection of the city, exactly which of the four cardinal directions (north, east, south or west) the cat will head. While this information is handy, you still don't know where all the cats currently are.

In order to prove the cost-effectiveness of your method to the City it would, of course, be important to minimize the number of traps used.

Input

The input will begin with a line consisting of two numbers n and m, separated by a space (1 ≤ n, m ≤ 1000). The city will be an n x m grid of square subsections. The next n lines will each consist of a string of length m, consisting of the letters 'N', 'E', 'S', or 'W', representing north, east, south and west, respectively. (The first character of the first line will be the northwesternmost point.) The direction in the square is the direction which cats will head if they are in that square. The cat psychologist assures you that cats have no interest in leaving the city.

Output

Output the minimum number of traps needed.

Example

Input:
3 4
SWWW
SEWN
EEEN

Output:
2

hide comments
Chirag Gupta: 2014-01-13 19:30:30

used scanf instead of getline and got AC..!!

These test cases might be useful:
4 4
SWWW
SEEW
SSWS
NNWN

Answer -> 4
Groups:
1 1 1 1
1 2 2 2
1 3 3 4
1 3 3 4

--------------------------------
4 20
SWWWSEEWSSESSWWWSEEW
SWWWSEEWSSESSWWWSEEW
SWWWSEEWSSESSWWWSEEW
NEEEEWEWWEWEWEWEEWWN

Answer->13

Groups:
1 1 1 1 2 3 3 3 4 5 6 6 6 6 6 6 7 8 8 8
1 1 1 1 2 9 9 9 4 5 6 6 6 6 6 6 7 10 10 10
1 1 1 1 2 11 11 11 4 5 6 6 6 6 6 6 7 12 12 12
1 2 2 2 2 2 4 4 4 5 5 6 6 13 13 7 7 7 7 12

Last edit: 2013-09-20 09:39:03
LeppyR64: 2013-09-03 16:31:13

The input format is correct. Akhilesh has not considered that there a multiple types of EOL. This problem has CRLF at the end of line. Not just LF.

Akhilesh Anandh: 2013-08-31 15:34:30

Bad input format. Got WA with getchar(); accepted with scanf("%s").
@Problem setter: Please look into it.

Last edit: 2013-08-31 15:36:41
mala da.... annamala: 2013-07-15 10:36:03

Simple logic is enough....

nagato: 2013-06-19 19:34:45

easy one ...:)

ankit agarwal: 2013-04-28 05:21:30

sudipto das
answer for your query is 1!

Shubhdeep: 2012-12-23 20:16:02

Nice problem :))

Last edit: 2012-12-23 20:20:37
gourav: 2012-12-15 09:21:57

my new friend: spoj.. luv you spoj :-) learning alot from you.. thank you

Last edit: 2012-12-15 09:27:11
P$ycH0-c0d(-R: 2012-12-02 07:23:12

what if both n=1,m=1..???


Added by:JaceTheMindSculptor
Date:2009-04-07
Time limit:0.902s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Canadian Computing Competition 2008 Stage 2 Day 2 Problem D