나인 나이트
시간 제한1초메모리 제한1024 MB
5x5 체스판에 나이트가 9개 있고, 서로 나이트의 이동 규칙으로 공격하지 않는지 판별합니다.
문제
체스에서 나이트는 독특하지만 힘은 강하지 않은 말이다. 다른 말 중에 나이트처럼 L자 모양으로 움직이는 말은 없다. 나이트는 어느 방향으로든 L자 모양으로 움직인다. 가로로 두 칸 가고 세로로 한 칸 위나 아래로 가거나, 세로로 두 칸 위나 아래로 가고 가로로 한 칸 간다.
그림 1: 강조된 칸은 나이트가 갈 수 있는 모든 칸을 나타낸다.
나이트는 한 번 움직일 때마다 자신이 서 있는 칸의 색이 바뀐다. 밝은 칸에서 출발하면 움직인 뒤에는 어두운 칸에 도착한다. 그림에서 나이트는 빨간 칸 중 어느 곳으로든 갈 수 있다.
보드에 놓을 수 있는 나이트의 최대 개수는 다음과 같다.
나인 나이트 문제에서는 최대 13개를 놓을 수 있는 5×5 보드에 나이트 9개를 놓는다. 나이트들이 서로 공격하지 않도록 놓는다. 아래 보드는 잘못된 해이다.
...k.
...k.
k.k..
.k.k.
k.k.k
입력
첫 줄에 테스트 케이스의 개수가 주어진다. 이어서 각 테스트 케이스는 5×5 보드를 다섯 줄의 문자로 나타낸다. 각 줄은 '.'과 'k' 문자로만 이루어진다. '.'은 빈 칸, 'k'는 나이트를 뜻한다. 보드 사이에는 빈 줄이 없다.
출력
테스트 케이스마다 한 줄을 출력한다. 주어진 보드가 나인 나이트 문제의 올바른 해이면 "valid"를, 그렇지 않으면 "invalid"를 출력한다.