Informatica Online Judge

  잠수함 식별 3 [0990 / 03DE]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 59   Total Tried : 137


The Champion of this Problem (C++) : gs17044 - ms / 620byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background



이번에 경곽이가 개발한 패턴감지기는 어떤 패턴을 다음과 같은 신호로 표현한다.

숫자 0과 1 ~, | , ( )

먼저 "~"의 의미는 그 문자를 반복한다는 의미이다. 예를 들어 1~는 "1", "11", "111...1" 모두 가능하다.

(10)~ 은 "10", "1010", "1010.. 10" 등이 모두 가능하다.

다음으로 "|" , "( )"의 의미는 다음과 같이 이용된다.
1~ | (10)~ 는 "11", "111010" 등 이 모두 가능하다.

자세한 설명은 [잠수함 식별] 문제를 참고한다.

잠수함 신호를 나타내는 패턴은 다음과 같다.

( 100~1~ | 01 )~

위 패턴을 만족하면 모두 잠수함의 신호로 판단할 수 있다.

N*N행렬이 주어진다.

이 행렬의 원소는 { 0, 1 }이다.

예를 들어 N = 2이고 행렬의 값이 다음과 같다고 가정하자.

1 0
1 0

위 행렬에서 행과 열이 중복되지 않도록 N개의 원소를 1행부터 N행 순으로 골라 하나의 패턴을 만든다.

행과 열을 중복되지 않도록 고른다는 의미는 1행에서 1열을 골랐으면, 1행이 들어가는 모든 열과, 1열이 들어가는 모든 행을 더 이상 고를 수 없다는 의미이다.

이 조건을 만족하면 서 골랐을 때
(1행 1열), (2행, 2열)을 고르면 "10"이 되고
(1행 2열), (2행 1열)을 고르면 "01"의 2가지 경우만 가능하다.

이 중 잠수함 패턴이 되는 경우 "01"의 한 가지 뿐이다.

따라서 위 행렬에서 가능한 잠수함 패턴의 수는 1이다.

N*N행렬이 주어질 때, 각 행과 열이 중복되지 않도록 길이 N패턴을 만들 때, 가능한 모든 잠수함을 구성할 수 있는 경로의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 행과 열의 수를 나타내는 정수 N이 입력된다.

두 번째 줄부터 N줄에 걸쳐서 각 줄에 N개의 0또는 1이 입력된다.

[입력값의 정의역]
2 <= N <= 20

[Sub task Info]
#1 : 1 <= N <= 7
#2 : N <= 13
#3 : N <= 15
#4 : N <= 20

Output

가능한 잠수함패턴을 만드는 경로의 수를 100,000,007 로 나눈 나머지를 출력한다.

IO Example

입력
2
1 0
1 0

출력
1

입력2
3
1 1 0
0 1 0
1 1 1

출력2
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]