27741번 - 견제 미로찾기 서브태스크

$N \times N$ 크기의 격자로 표현되는 미로가 있다. 미로의 좌상단은 $(1,1)$이며 우하단은 $(N,N)$이다. $0$은 이동할 수 있는 길, $1$은 이동할 수 없는 벽이 있는 칸을 의미한다. 초기에 하나의 게임 말이 $(1,1)$에 위치해있다. 건이와 준성이는 번갈아가면서 다음 두 개의 행동 중 하나를 취할 수 있다.

1. 게임 말을 $x$ 또는 $y$ 좌표가 증가하는 방향으로 $1$ 이상 $K$ 이하만큼 한 방향으로만 이동한다. 벽이 있는 칸에 도착하거나, 벽을 통과하여 이동할 수 없다.
2. $K$를 $K$보다 작은 $K$의 양의 약수 중 하나로 변경한다.

자신의 차례에 아무 행동도 할 수 없는 사람이 패배한다. 게임은 건이부터 시작하며 두 사람이 최선을 다해 게임을 진행했을 때, 누가 이길지 구하시오.

첫 번째 줄에 $N$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 미로의 정보가 공백으로 구분되어 주어진다.

건이가 이긴다면 $1$, 준성이가 이긴다면 $0$을 출력한다.

• $1 \leq N \leq 300$
• $1 \leq K \leq N$
• $N$, $K$는 양의 정수이다.
• 미로는 $0$ 혹은 $1$로 이루어져 있다.
• 미로의 $(1,1)$은 $0$임이 보장된다.