17492번 - 바둑알 점프 서브태스크

바둑알 점프는 판 위에 있는 바둑알을 하나만 남기고 모두 없애는 게임이다. 바둑알은 가로, 세로, 대각선으로 인접한 바둑알 하나를 점프하여 움직일 수 있다. 움직였을 때, 뛰어넘은 바둑알은 없어진다. 이때 뛰어넘을 바둑알이 없으면 움직일 수 없다.

예를 들어, [그림1]에서 왼쪽 상단 바둑알을 오른쪽 하단 대각선 방향으로 움직이면 [그림2] 와 같이 된다. [그림3]에서 오른쪽 하단에 있는 바둑알은 뛰어 넘을 바둑알이 없으므로 움직일 수 없다.

바둑알이 놓이는 판은 N × N의 정사각 행렬이고 한 칸은 1 × 1 행렬이다. 판은 빈 칸 혹은 벽으로 구성된다. 바둑알은 항상 빈 칸으로만 이동할 수 있고 벽을 뛰어넘을 수 없다. 바둑알이 없어진 칸은 빈 칸이 된다. 바둑알 점프는 바둑알 하나를 골라 점프하여 바둑알 하나를 없애고 다시 남은 바둑알들 중에 하나를 골라 점프하는 행위를 반복하여 바둑알을 1개만 남기면 승리한다.

판 위에 바둑알의 배치 정보가 주어진다. 바둑알 점프를 했을 때 승리할 수 있는지 판별하는 프로그램을 작성하라.

입력의 첫 줄에 양의 정수 N이 주어진다. 이는 N × N 정사각 행렬의 한 변의 길이이다. 그 다음 줄부터 N개의 줄에 걸쳐 판의 상태가 주어진다. 각 줄은 N개의 정수가 공백으로 구분되어 주어지는데, 각각의 정수는 0, 1 또는 2이다. 여기서 0은 빈 칸, 1은 벽, 2는 바둑알을 의미한다.

바둑알 점프를 하여 바둑알을 1개만 남길 수 있다면 Possible을, 불가능하다면 Impossible을 출력한다.

• 3 ≤ N ≤ 10
• 입력으로 주어지는 판의 둘레에 있는 칸들은 모두 벽이며, 모든 바둑알은 빈 칸에 위치한다.

• 바둑알의 수가 1 이상 2 이하이다. 

• 바둑알의 수가 1 이상 7 이하이다.