Dfs not working!

problem: USACO
my code: https://ideone.com/e.js/9mxjC0
I was trying to solve it using binary search and dfs (flood fill) but I am not able to pass certain tests! could you please tell me the reason?
The official tutorial pointed out that dfs is risky due to depth of recursion but I don’t understand why, aren’t the constraints not that much big (500*500).

Generally, when should I avoid using dfs and use bfs instead?

The depth of recursion can go up to NM which is too deep.

This is misleading. It is definitely possible to pass this problem with DFS.

Note: If you run a DFS solution locally on test cases of the maximum size, you might see segmentation faults (see C++ With the Command Line). This is because the default stack size limit might be very small (say, 8MB). However, when your solution is judged on USACO (and most other online judges), there is no stack size limit other than the memory limit (256MB for USACO).

If the grid is very large (say, 4000\times 4000) and the memory limit is tight, BFS might pass when DFS does not. However, you almost always do not need to worry about this.

I would suggest trying to figure this out on your own (e.g., by stress testing against the model solution):

1 Like