Building a Binary Grid

$N \geq 5$에서는 기본적으로 각 행을 0, 1, 0, 1, $\ldots$로 채운다. 같은 문자가 이어지면 오른쪽으로, 문자가 바뀌면 위나 아래로 한 칸 이동하면 문자열을 만들 수 있다. 첫 번째 열은 값을 반대로 두어 완전히 번갈아 나오는 두 문자열을 모두 세로 경로로 처리한다.

첫 번째 열을 뒤집으면 전부 같은 문자인 문자열을 가로로 만들 수 없으므로 $(2,N)$을 0, $(3,N)$을 1로 바꾼다. 이 두 칸을 이용하면 00...0과 11...1도 만들 수 있다. 문자가 한 번만 바뀌는 경우에는 4, 5번째 행을 사용하고, 두 번 이상 바뀌는 경우에는 마지막 열에 닿지 않게 시작 행을 고르면 수정한 두 칸을 피할 수 있다.

$N \leq 4$에서는 칸이 최대 $16$개뿐이므로 모든 격자를 확인하고 깊이 우선 탐색으로 필요한 경로를 찾는다. 전체 출력 경로 생성에는 $O(NQ)$ 시간이 든다.