Erasing Dadas Strings

Take the leftmost column containing an unerased cell, then the topmost unerased cell $(r,c)$ in that column. This cell must be the first character of a Dadas string, so it must contain d.

If $(r+1,c)$ is still present and contains a, that cell cannot belong to a different string starting above or to the left. Therefore the current string must go downward. Otherwise it must go to the right. In the chosen direction, erase the first sequence that alternates d, a and then ends in s. Encountering an invalid or already erased cell makes the construction impossible.

Process all cells in column-major order. If every cell is erased, the recorded operations form a solution. Every cell is inspected once, so the time complexity is $O(NM)$.