It is easy to determine which type of animal traversed the area last. If the starting and ending square contain T, it was obviously a tiger, otherwise it must have been a bull. Also, observe that, if a minimal number of animals traversed the rectangular area then no two animals of the same kind went one after the other.

We will think about the problem "backwards". Let's find all the squares that could have been traversed by the last animal before it left the rectangular area. Those squares form a connected component (in four directions) of the same type of footprints. Since all of those squares could have been traversed by the previous animal, we can change the value of those squares to the footprint of another animal type and add ~1~ to the solution. We should repeat this process until all only a single type of footprint remains. Naive implementations of this algorithm should score 45 points.

Let's now represent each connected component of the same footprint type as a node in a graph. Two nodes are connected if their corresponding components are neighbours, meaning that there exist at least two neighbouring squares in the matrix such that one belongs to the first and the other belongs to the second component. This graph is actually a tree. If we root the tree in a component where the upper-left square belongs, then the number of iterations of the previous algorithm corresponds to the depth of that tree. The tree can be built in ~\mathcal O(RS)~ and the number of its nodes is bounded by the same expression.