hackercupai/hackercup

1The same impossible cases apply as before: one row or one column, with at least one tree.2 3Otherwise, we'll start by marking all non-rock cells as "good." Next, we'll mark all spaces with \(0\) or \(1\) good neighbors as "bad" in \(\mathcal{O}(RC)\) time. We can then run a breadth-first search from these initial bad spaces. At each BFS step, we check if a space is marked good, but currently has fewer than \(2\) good neighbors. If so, mark it as bad and enqueue its neighbors so they can later be checked for consistency, as each neighbor will now have one fewer good neighbor. When the BFS terminates, all good/bad markings will be consistent. Finally, we check if any tree in the original input is marked bad, in which case the answer is "`Impossible`". Otherwise, we can output a tree for all spaces marked good.4 5It can be observed that for every BFS step that branches, we are converting a different good cell to bad, of which there can be at most \(R * C\). Thus the BFS must terminate, and in worst-case running time \(\mathcal{O}(RC)\).6 7[See David Harmeyer's solution video here.](https://youtu.be/aC0n8sB2BLs)8