BFS or DFS

Posted by

svr 17 Nov 2008 20:56

BFS gave TLE 7.

DFS must be much more successful.

Reasons:

1) Easy to construct the son.

2) Easy and without memory reconstruct the father.

DFS-TLE10 Therefore exists some strong mathematics in the problem to speed up algos.

*Edited by author 18.11.2008 09:24*

Re: BFS or DFS

There exists very strong pruning idea, which makes brute-force extremely fast =)

Re: BFS or DFS

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?