4559 - Broken N-Queen(Challenge)

• Submit
• Status
• Discuss
• Summary

Description

N-Queen 문제를 풀려고 N × N 체스판 위에 퀸을 이리저리 올려보던 분조장씨는 체스판 샷건을 시전했다. 그 결과, 체스판이 중간중간 비어버리고 말았다.

망가진 N×N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 올려놓는 경우의 수를 구해보자. (단, 퀸은 체스판의 빈 공간에 둘 수 없으며, 빈 공간을 건너뛰어 공격할 수도 없다.)

Input

Line 1: 체스판 크기 N 입력 (1≤N≤9)

Line 2~N+1: 체스판 상태 입력. 1: 체스판, 0: 빈 칸

Output

Line 1: 퀸을 올려놓을 수 있는 경우의 수를 출력하고, 만약 N개의 퀸을 올려놓을 수 없는 경우, "IMPOSSIBLE"을 출력한다.

Sample Input

5
1 1 1 1 1
1 1 0 1 1
1 0 1 1 1
1 1 1 1 1
1 1 1 1 0

Sample Output

12

Hint

	Q
		X		Q
Q	X	Q
			Q	X

Q: 퀸, X: 빈 칸

이렇게 두는 게 가능하다.