Yes, DFS is the way for this problem. My AC 0.015 solution can solve a 20x20 in about 700 recursions.

Here's a hint for the problem:

Pay close attention to the following sentence: "If the number of bacteria in a certain cell becomes 5, then 4 of them die because of overcrowding.".

What would happen if this rule didn't exist?