밥의 집터

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

요약

N행 M열 높이 격자에서 모든 칸 높이가 같은 직사각형 배치 개수를 셉니다.

난이도: 보통10점 중 6점
유형: 스택, 행렬, 동적 계획법
정답자: 아직 제출이 없습니다

문제

밥은 이름난 건축업자다. 땅을 사서 그 위에 집을 지으려 하는데, 땅의 높이가 칸마다 달라서 문제가 생겼다.

땅은 직사각형이고 $N$ 개의 행과 $M$ 개의 열, 즉 $N \times M$ 개의 정사각형 칸으로 나뉜다. 밥이 지을 집도 직사각형이고, 네 변은 땅의 변과 평행하며 꼭짓점은 칸의 꼭짓점과 만난다. 집이 덮는 칸의 높이는 모두 같아야 한다. 높이가 다르면 집이 무너진다.

집을 지을 수 있는 방법이 몇 가지인지 구하라. 한 칸만 덮는 집도 한 가지로 센다.

입력

첫째 줄에 정수 $N$ 과 $M$ 이 주어진다. ( $1 \le N, M \le 1000$ )

다음 $N$ 개 줄에는 각각 정수 $M$ 개가 주어진다. $j$ 번째 수 $a_{ij}$ 는 $i$ 번째 행 $j$ 번째 칸의 높이다. ( $1 \le a_{ij} \le 10^9$ )

입력의 양이 매우 많으므로 빠른 입력 방법을 쓰는 편이 좋다. 예를 들어 C++에서는 cin 대신 scanf를, Java에서는 Scanner 대신 BufferedReader를 쓴다.

출력

집을 지을 수 있는 방법의 수를 한 줄에 출력한다.

힌트

첫 번째 예제에서 가능한 집터를 몇 가지 들면, 마주 보는 두 꼭짓점이 (0,0)과 (1,1)인 직사각형과 (0,0)과 (0,2)인 직사각형은 높이가 2이고, (2,0)과 (2,2)인 직사각형과 (1,2)와 (2,2)인 직사각형은 높이가 1이다. 괄호 안의 첫 번째 수는 행 번호, 두 번째 수는 열 번호이며 0부터 센다.

예제9

예제 1
입력
```
5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1
```
예상 출력
```
27
```
예제 2
입력
```
4 3
1 1 1
1 1 1
2 2 2
2 2 2
```
예상 출력
```
36
```
예제 3
입력
```
1 1
1000000000
```
예상 출력
```
1
```
예제 4
입력
```
1 5
1 2 3 4 5
```
예상 출력
```
5
```
예제 5
입력
```
1 6
7 7 7 7 7 7
```
예상 출력
```
21
```
예제 6
입력
```
6 1
4
4
4
4
4
4
```
예상 출력
```
21
```
예제 7
입력
```
4 4
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1
```
예상 출력
```
16
```

예제 8

입력

2 3
1 1000000000 1000000000
1 1000000000 1

예상 출력

예제 9
입력
```
3 4
5 5 3 3
5 5 3 1
2 2 2 1
```
예상 출력
```
23
```