33959번 - 쿼리도

쿼리도란 $N \times N$ 격자로 구성된 게임판에서 두 선수가 번갈아 말을 움직이거나 칸 사이에 길이가 $2$인 벽을 가로 혹은 세로로 두는 것을 반복하며 진행되는 게임이다. 길이가 $2$인 벽을 둘 때는 가로벽과 세로벽이 서로 교차하게 두거나, 기존에 두어진 벽과 겹치게 두거나, 벽의 일부가 격자 밖으로 나가도록 둘 수는 없다. 게임판의 $x$번째 행 $y$번째 열을 $(x,y)$라 하자.

쿼리도를 누구보다 사랑하는 POSCAT 부원들은 매년 쿼리도 챔피언십을 개최해왔다!

심판을 맡은 당신의 역할은 게임이 끝난 게임판의 벽 배치를 바탕으로 올바른 게임이었는지 판단하는 것이다.

예를 들어 $N=4$일때, 다음 게임판들은 길이 $2$의 벽을 반복해서 두어 만들어 질 수 있으므로 올바른 게임을 통해 만들 수 있는 게임판이다.

올바른 게임에서 나올 수 있는 벽 배치 상태

하지만, 다음 게임판들은 길이 $2$의 벽만으로는 만들 수 없거나 길이 $2$의 벽을 교차해서 두어야 하므로 올바른 게임을 통해 만들 수 없는 게임판이다.

올바른 게임에서 나올 수 없는 벽 배치 상태

게임판의 벽 배치 상태가 주어질 때, 서로 겹치거나 교차할 수 없는 길이가 $2$인 벽을 계속해서 두어서 만들 수 있는 게임판이라면 YES, 만들 수 없는 게임판이라면 NO를 출력하여라.

첫 번째 줄에 게임판의 크기 $N$이 주어진다. ($2 \le N \le 50$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $N-1$개의 정수 $A_{i,1}, \cdots, A_{i,N-1}$이 공백으로 구분되어 주어진다. $A_{i,j}$는 $(i,j)$와 $(i,j+1)$ 사이에 벽이 있다면 $1$, 그렇지 않다면 $0$이다.

$N+2$ 번째 줄부터 $N-1$개의 줄에 걸쳐 $N+1+i$번째 줄에 $N$개의 정수 $B_{i,1}, \cdots, B_{i,N}$이 공백으로 구분되어 주어진다. $B_{i,j}$는 $(i,j)$와 $(i+1,j)$ 사이에 벽이 있다면 $1$, 그렇지 않다면 $0$이다.

주어진 게임판이 올바른 게임을 통해 만들 수 있는 게임판이라면 YES, 불가능하다면 NO를 출력하여라.