상현이는 유명한 건축가이다. 최근 자신의 집을 짓기 위하여 땅을 구입했다. 구입한 땅은 다양한 굴곡이 있었는데 자연 친화적인 건축을 하는 상현이는 땅의 형질을 그대로 이용하고자 한다. 하지만 건물은 같은 높이에서만 지을 수 있으므로 땅의 어느 곳을 선택하느냐에 따라 건물을 짓는 여러 가지 경우의 수가 생긴다. 상현이가 구입한 땅을 격자 형태로 나누어 본 결과 아래 그림과 같다고 하자. 이때 상현이는 하나의 격자 또는 상하 좌우 인접한 영역의 같은 높이의 격자를 선택하여 직사각형 모양의 지역에 건물을 세우고자 한다. 따라서 아래 (1)번 그림처럼 빨간색이나 파란색으로 칠해진 곳에는 건물을 세울 수 있다. 반면 (2)번, (3)번 그림과 같은 영역은 세울 수 없다.

위 예제의 경우 높이 1인 격자에 건물을 세우는 경우가 12가지, 높이 2인 격자에 건물을 세우는 경우가 15가지 모두 27가지 경우가 존재한다.

상현이가 구입한 토지에 대한 정보가 주어질 때 상현이가 건물을 세우는 방법이 몇 가지인지 구하는 프로그램을 작성하시오.

#2888 upload 7 done 4 how_to_reg 3

어떻게 집을 지을까(BOB) timer 1s memory 128MB

#2888

어떻게 집을 지을까(BOB) 1s 128MB