연꽃 키우기 1

문제 배경

궁남지는 부여군을 대표하는 관광지로, 신라 선화공주와 결혼한 백제 무왕의 서동요 전설이 깃든 우리나라 최고(最古)의 인공정원이다.

연꽃 특성:

• 모든 꽃은 다음날 동시에 번식한다.
• 현재 꽃의 위치에서 인접한 곳(상하좌우)이 비어 있으면, 그 위치들로 번식한다.
• 번식하지 못한 연꽃은 사라진다.

문제

h행 w열의 연못이 있다. 초기에 (x, y) 위치(0-indexed)에 연꽃 한 송이가 있다.

매일 각 연꽃은 상하좌우 네 방향으로 번식한다. 번식하지 못한 꽃(사방이 꽃이거나 연못 경계 밖인 경우)은 사라진다.

n일 후 연꽃의 수를 구하시오.