SPOJ #4177. Herding editorial

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.