귀농
시간 제한1초메모리 제한256 MB
N x N 격자에서 정확히 한 꼭짓점에서만 맞닿고 합이 서로 같은 두 직사각형을 고르는 방법의 수를 구하는 문제입니다.
문제
두 사람이 도시를 떠나 친구의 정사각형 농지에서 농사를 짓기로 했다. 농지의 크기는 N x N이고, 1 x 1 크기의 칸으로 나누어져 있다. 칸 (i, j)의 수익은 Aij이며, 이 값은 음수일 수도 있다.
친구는 두 사람에게 각각 비어 있지 않은 직사각형 모양의 땅을 하나씩 빌려주려고 한다. 각 직사각형의 변은 격자선과 평행해야 한다.
친구는 두 직사각형의 수익 합이 같도록 땅을 나누려 한다. 또한 두 땅이 변을 공유하지 않게 하면서 경쟁심을 유지하기 위해, 두 직사각형은 꼭짓점 하나에서만 만나야 한다. 두 직사각형은 겹치거나 변의 일부를 공유할 수 없다.
조건을 만족하는 두 직사각형을 고르는 방법의 수를 구하라. 두 사람을 서로 바꾸어 배정한 것은 새로운 방법으로 세지 않는다.
입력
첫째 줄에 농지의 크기 N (1 <= N <= 50)이 주어진다.
다음 N개의 줄에는 각각 N개의 정수가 주어진다. i번째 줄의 j번째 정수는 칸 (i, j)의 수익 Aij이다 (-1000 < Aij < 1000).
출력
조건을 만족하도록 두 직사각형을 빌려주는 방법의 수를 출력한다.
힌트
첫 번째 공개 테스트에서, 칸 좌표를 0부터 시작하고 직사각형의 양 끝점을 모두 포함한다고 하면 가능한 쌍은 다음과 같다.
(0,0)-(1,1),(2,2)-(2,2)(1,0)-(1,0),(0,1)-(0,1)(2,0)-(2,0),(1,1)-(1,1)(1,1)-(1,1),(0,2)-(0,2)(2,1)-(2,1),(1,2)-(1,2)(2,0)-(2,1),(0,2)-(1,2)(1,0)-(2,0),(0,1)-(0,2)