The question asks for the number of disjoint groups in which the cats can move. For a cat in a square, it always moves in one direction of {North, South, East, West}. It is provided that cats never go outside the city. This information is helpful in building a simple solution using stl in C++.

- Take the input matrix in an array of strings.
- Make a map(squares) with each index as key and random value(say 1) as its value. map< pair<int,int>, int > squares. (squares will have N*M elements.)
- Take an empty array(A) of size N*M. int A[N][M].
- Take an empty vector(V) and a variable “temp” initialised to 1.
- Run a loop until the map is not empty.
- Add a random value(say 1) into vector V.
- Take the key of first element of map(squares) and run a loop // to trace the path along with given directions.
- Mark the index in A with value of temp.
- Erase the element from map having the key as the current index.
- Find the next index according to the direction given in current index.
- If next index is already visited and has a value less than temp, remove an element from vector V and come out of loop.
- If next index is already visited with the same value as temp, just come out of loop.
- If next index is not visited, continue the loop.

- Increment value of temp.

- The size of vector V is the answer.

The reason for why size of vector is the answer? We are incrementing number of groups by 1 whenever we find a new group, by adding an element into the vector. If we find that a group leads to an already traversed group, we are not counting that group by removing an element from the vector.

Coding is left for you. Leave a comment to this post if you have any difficulty in understanding or in coding.

Link to the problem HERDING.

Advertisements