COCI 2013/2014 - Contest 1- 직사각형 (RATAR) > 문제은행 : 정보올림피아드&알고리즘




2680 : 직사각형 (RATAR)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
13 회   
시도횟수
26 회   

문제

N x N의 정사각형 격자의 각 칸에 -1,000보다 크고 1,000보다 작은 수가 써져 있다. 이 때 직사각형 두 개를 아래 조건을 만족하게 그리는 방법의 수를 구하는 프로그램을 작성하여라.

1) 두 직사각형은 격자를 공유하거나 변을 공유하지는 않지만 꼭짓점을 공유한다.

2) 두 직사각형을 둘러싸는 격자에 있는 수들의 합이 서로 같다.



입력형식

첫 번째 줄에는 격자의 크기 N이 주어진다. (1 ≤ N ≤ 50)
두 번째 줄부터 N개의 줄에는 각 격자에 적힌 수가 주어진다.


출력형식

조건을 만족하게 두 직사각형을 만드는 방법의 수를 출력한다.


입력 예

3
1 2 3
2 3 4
3 4 8

출력 예

7

입력 예

4 
-1 -1 -1 -1
1 2 3 4
1 2 3 4
1 2 3 4

출력 예

10

입력 예

5 
-1 -1 -1 -1 -1
-2 -2 -2 -2 -2
-3 -3 -3 -3 -3
-4 -4 -4 -4 -4
-5 -5 -5 -5 -5

출력 예

36

Hint!

첫 번째 예제의 가능한 사각형 쌍은 다음과 같다.
0,0)-(1,1) and (2,2)-(2,2), (1,0)-(1,0) and (0,1)-(0,1), (2,0)-(2,0) and (1,1)-(1,1), (1,1)-(1,1) and (0,2)-(0,2), (2,1)-(2,1) and (1,2)-(1,2), (2,0)-(2,1) and (0,2)-(1,2), (1,0)-(2,0) and (0,1)-(0,2).




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP