Dfs not working!

[ATh3tr]

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?

[Benq]

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).

@ATh3tr

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

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.

@ATh3tr

I was trying to solve it using binary search and dfs (flood fill) but I am not able to pass certain tests!

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

@thecodingwizard

We expect that you have read through the entire Debugging module before posting.

• If it’s a problem with publicly available test data (ex. USACO), we expect that you’ve checked the test case(s) on which your code is failing.
• We expect that you’ve tried stress testing to generate a small test case on which your solution fails (as described in the module).