다다스 문자열 지우기

아직 남은 칸이 있는 가장 왼쪽 열을 고르고, 그 열에서 가장 위에 남은 칸 $(r,c)$를 보자. 이 칸은 어떤 다다스 문자열의 첫 글자여야 하므로 반드시 d이다.

$(r+1,c)$가 아직 남아 있고 a라면 그 칸은 왼쪽이나 위쪽에서 시작한 다른 문자열에 포함될 수 없다. 따라서 현재 문자열은 아래쪽으로 진행해야 한다. 그렇지 않으면 오른쪽으로 진행해야 한다. 정한 방향으로 d, a가 번갈아 나오다가 s로 끝나는 가장 앞의 문자열을 지운다. 이 과정에서 규칙에 맞지 않는 칸이나 이미 지운 칸을 만나면 불가능하다.

열 우선 순서로 모든 칸을 처리한 뒤 전부 지워졌으면 기록한 연산들이 답이다. 각 칸은 한 번만 확인되므로 시간 복잡도는 $O(NM)$이다.