COCI 2014/2015 contest2 4- 어떻게 집을 지을까(BOB) > 문제은행 : 정보올림피아드&알고리즘




2888 : 어떻게 집을 지을까(BOB)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
2 회   
시도횟수
11 회   

문제

상현이는 유명한 건축가이다. 최근 자신의 집을 짓기 위하여 땅을 구입했다. 구입한 땅은 다양한 굴곡이 있었는데 자연 친화적인 건축을 하는 상현이는 땅의 형질을 그대로 이용하고자 한다. 하지만 건물은 같은 높이에서만 지을 수 있으므로 땅의 어느 곳을 선택하느냐에 따라 건물을 짓는 여러 가지 경우의 수가 생긴다. 상현이가 구입한 땅을 격자 형태로 나누어 본 결과 아래 그림과 같다고 하자. 이때 상현이는 하나의 격자 또는 상하 좌우 인접한 영역의 같은 높이의 격자를 선택하여 직사각형 모양의 지역에 건물을 세우고자 한다. 따라서 아래 (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 이다.

출력형식

상현이가 건물을 지을 수 있는 경우의 수를 출력하시오.

입력 예

5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1

출력 예

27

입력 예

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

출력 예

36


경기도 안양시 동안구 평촌대로 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