네모난 순열 찾기 1

시간 제한1초메모리 제한1024 MB

요약

N이 15 이하인 N×N 격자에서, 안에 든 수들이 1부터 칸 수까지의 순열을 이루는 축에 나란한 부분 직사각형의 개수를 센다.

난이도: 보통10점 중 7점
유형: 완전 탐색, 배열, 수학, 누적 합
정답자: 아직 제출이 없습니다

문제

$N^2$ 개의 수가 $N$ 행 $N$ 열의 표 $A$ 에 채워져 있다. 표의 위에서부터 $r$ 번째 행, 왼쪽에서부터 $c$ 번째 열에 위치한 칸에는 정수 $A\_{r,c}$ 가 적혀 있으며, $r$ 행 $c$ 열을 편의상 $(r,c)$ 로 표현한다.

표 $A$ 에서 직사각형 맨 왼쪽 위 칸이 $(r\_1,c\_1)$ 이고, 맨 오른쪽 아래 칸이 $(r\_2,c\_2)$ 가 되게 직사각형을 선택할 때, $1\leq r\_1\leq r\leq r\_2\leq N,1\leq c\_1\leq c\leq c\_2\leq N$ 을 만족하는 $A\_{r,c}$ 는 직사각형 안에 있는 수이다.

수 $x$ 개로 이루어진 배열이 $1$ 부터 $x$ 까지의 서로 다른 정수 $x$ 개로 이루어져 있다면, 순열이다. 예를 들어 $\[2,3,1,5,4]$ 는 순열이지만, $\[1,2,2]$ 와 $\[1,3,4]$ 는 순열이 아니다.

직사각형의 네 변이 표의 경계선과 겹치도록 직사각형을 선택할 때, 직사각형 안에 있는 수를 나열한 것이 순열이 되는 경우의 수는 얼마일까?

입력

첫째 줄에 표 $A$ 의 행과 열의 개수 $N$ 이 주어진다. ( $1\leq N\leq 15$ )

이후 $N$ 개의 줄에 걸쳐 $i+1$ 번째 줄에 $A\_{i,1},A\_{i,2},\ldots ,A\_{i,N}$ 이 공백으로 구분되어 주어진다. ( $1\leq A\_{i,j}\leq N^2$ )

출력

첫째 줄에 경우의 수를 출력한다.

예제1

예제 1
입력
```
4
1 2 1 5
3 1 8 1
1 2 1 3
3 1 4 1
```
예상 출력
```
16
```