Quote:
Originally Posted by goofyballer
None of this really makes sense to me, because I visualize trees as being very different from grids. Like, for this:
1,0 and 0,1 both have 1,1 as children, so that becomes weird in the context of traversal algorithms.
It's really a graph rather than a tree
Quote:
Going back to the potential solution I described earlier:
Would you describe this as BFS, DFS, or neither? (I think it's O(n) for some multiple of n but I'm not positive)
Whether this is BFS or DFS sort of depends on the nature of your recursion. You can reorder recursive visiting functions to turn them from BFS to DFS and back.
I honestly go back and forth a bit on whether it's O(n^2) or maybe it's better. Naively it's O(n^2) because you have to visit n cells and for each cell you have to find all connected pieces which is coupled to the size of n also. For a signifcant number of searches, you'll get to quit early - a lot of the ones you quit early, you get to quit in constant time (if the cell is already covered, or if all it's neighbors are covered). So the question is, are the constant-time cell visits proportional to n? So the real answer might be O(nlogn) or O(n sqrtn) or something. I don't think it can be O(n) though
On the ****ty job front: I mostly think of myself as having a "good job" and I sort of think of that of a lot of my past jobs too. But also, I have quit almost all the jobs I had because I didn't want to work there any more, so at least at some times, I've thought almost every job I had sucked. For me I guess I go through cycles, if other people are the same then I guess at some point a percentage of us will describe our jobs as ****ty.