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.


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 the minimum number of traps needed.


3 4


hide comments
haiderbaig: 2019-03-14 14:13:34

Solved by creating a 2D array and traversing it according to the direction mentioned on the cells. Also have to keep track of visited cells.
I don't know how this is a DFS problem !

ab_biswas09: 2019-01-16 20:29:47

Solved using DFS by keeping track of visited nodes in the current recursion stack

suyashky: 2018-12-25 20:39:43

Similar questions to try (SPOJ questions):
UCV2013H - Slick
KOZE - Sheep

manishjoshi394: 2018-11-01 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.

Thank you for test cases!
@Chirag Gupta

Reposting for convenience...

4 4

Answer -> 4
1 1 1 1
1 2 2 2
1 3 3 4
1 3 3 4

4 20


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: 2018-11-01 15:45:40
salman3007: 2018-09-27 17:26:26

union find algo rocks.

sinersnvrsleep: 2018-03-25 06:02:36

be careful the cat might start from any cell

arjun8115: 2018-02-23 12:58:39

Use flood-fill algo.

nadstratosfer: 2017-10-24 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.

Edit: Came back several months older and got AC after having thrown _everything_ I had at it. The key was reducing memory use which is typically beyond obscene in PyPy (my AC solution uses 200MB on top of the standard 117MB bare interpreter overhead, compared to 350MB in my first attempt). Shame SPOJ doesn't allow different TL per language, many interesting graph problems are simply impossible to AC in Python when the grid gets big as we have no way of representing it efficiently in memory. F*****g "objects"!

Edit 20180302: Optimized my solution to run at over twice the last AC speed, and it still can TLE on one of the testfiles depending on server lags. Stupid, stupid time limit..

Last edit: 2018-03-02 08:43:42
ab_hi_shek111: 2017-09-25 11:15:18

simple DFS + logic :)

jatin03: 2017-07-11 18:24:15

Did it in second attempt dfs :)

Added by:JaceTheMindSculptor
Time limit:0.195s-0.902s
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