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 squareshaped 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 costeffectiveness 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
manishjoshi394:
20181101 15:42:16
BEWARE! Your dfs might not be covering all cells in one connected component, if you think your solution is right but don't get AC, try these cases.


salman3007:
20180927 17:26:26
union find algo rocks. 

sinersnvrsleep:
20180325 06:02:36
be careful the cat might start from any cell 

arjun8115:
20180223 12:58:39
Use floodfill algo. 

nadstratosfer:
20171024 08:19:28
Enjoyed optimizing my Python solution, too bad it still won't pass. In C, best time is 0.00 and people still get AC at 0.80+s. This is just stupid.


ab_hi_shek111:
20170925 11:15:18
simple DFS + logic :) 

jatin03:
20170711 18:24:15
Did it in second attempt dfs :) 

naks:
20170711 17:56:36
use disjoint sets!!! no bfs....


shahzada:
20170625 08:16:51
DFS. 

adityaghosh96:
20170618 23:00:20
Disjoint Sets. If you use 2d pair 2d array for roots, write the FindRoot function carefully. 
Added by:  JaceTheMindSculptor 
Date:  20090407 
Time limit:  0.195s0.902s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Canadian Computing Competition 2008 Stage 2 Day 2 Problem D 