문제
상현이는 유명한 건축가이다. 최근 자신의 집을 짓기 위하여 땅을 구입했다. 구입한 땅은 다양한 굴곡이 있었는데 자연 친화적인 건축을 하는 상현이는 땅의 형질을 그대로 이용하고자 한다. 하지만 건물은 같은 높이에서만 지을 수 있으므로 땅의 어느 곳을 선택하느냐에 따라 건물을 짓는 여러 가지 경우의 수가 생긴다. 상현이가 구입한 땅을 격자 형태로 나누어 본 결과 아래 그림과 같다고 하자. 이때 상현이는 하나의 격자 또는 상하 좌우 인접한 영역의 같은 높이의 격자를 선택하여 직사각형 모양의 지역에 건물을 세우고자 한다. 따라서 아래 (1)번 그림처럼 별색으로 칠해진 곳에는 건물을 세울 수 있다. 반면 (2)번, (3)번 그림과 같은 영역은 세울 수 없다.
위 예제의 경우 높이 1인 격자에 건물을 세우는 경우가 12가지, 높이 2인 격자에 건물을 세우는 경우가 15가지 모두 27가지 경우가 존재한다.
상현이가 구입한 토지에 대한 정보가 주어질 때 상현이가 건물을 세우는 방법이 몇 가지인지 구하는 프로그램을 작성하시오.
입력
첫 행에 행과 열의 크기를 나타내는 N, M( 1≤ N, M ≤ 1000)이 공백으로 구분하여 입력된다.
다음 N행 M열에 토지의 정보 Vij (1 <= Vij <= 1,000,000,000)가 입력된다.
입력의 20%는 1≤ N, M ≤ 50 이다.
입력의 50%는 1≤ N, M ≤ 500 이다.
출력
상현이가 건물을 지을 수 있는 경우의 수를 출력하시오.
예제1
입력
53
222
221
111
212
121
출력
27
예제2
입력
43
111
111
222
222
출력
36
출처
COCI 2014/2015 contest2 4