407926: GYM102944 C Canton

Exotic Canton, home to shopping plazas and stores... many, many stores. Especially large furniture stores. You are a manager of one these large furniture stores (one that sells just furniture, no meatballs). It is time for you to design a new "in-store shopping route" for your customers. The entire store can be represented by an $$$N\times M$$$ grid of square blocks. Each block is a $$$20$$$ foot by $$$20$$$ foot square space featuring one special type of furniture. You have come up with several design plans. In each of the plans, there is a "suggested walking direction" in every block pointing to one of the four neighboring blocks. We will use characters 'N', 'S', 'E', and 'W' for each of the four directions north, south, east, west.

A customer entering your store is supposed to pick an arbitrary block, then start following the suggested directions from block to block. Unfortunately, it may sometimes happen that the customer is not able to exit the store by doing this. Please count the number of blocks such that a customer starting from that block and following the suggested walking directions will never exit the store.

The first line in each input file contains two integers $$$N$$$ and $$$M$$$ ($$$1\le N, M\le 2000$$$). In each of the next $$$N$$$ lines there is a string of length $$$M$$$, composed of characters in {'N', 'S', 'E', 'W'}. As usual, the characters in each line are arranged from west to east and the lines are arranged from north to south.

Please output the number of starting blocks from which it is not possible to exit the store.

3 3
SSW
NSE
NWS

7

3 4
SWNW
EEEN
NWWW

0

10 9
NENSSNWSN
NSEEESNWE
NWESSSEEE
ESNNSEWNE
WNEWENSWW
SNNWESENS
SNNWSSWNW
ESNEEESSN
NEWSSESWW
NNWNENWWW

70