페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8206

파파야 정글 1초 1024MB

문제

Bessie는 농장에서 벗어나 이웃 농부의 땅으로 가게 되었습니다. 그 농부는 맛있는 파파야를 재배하는데, 이는 소들이 좋아하는 별미입니다.

파파야 정글은 R개의 행과 C개의 열로 이루어진 격자로 나누어져 있습니다. Bessie는 주어진 칸에서 X축 또는 Y축을 따라 인접한 칸으로 이동할 수 있습니다. 예를 들어, 아래와 같은 다이어그램에서 Bessie가 'B'라고 표시된 칸에 있다면, 'T'로 표시된 인접한 칸으로 이동할 수 있습니다:

.T.
TBT
.T.

Bessie는 항상 (행=1, 열=1) 위치에서 파파야를 먹기 시작합니다. 한 칸에서 먹이를 다 먹은 후, Bessie는 항상 인접한 칸에서 보이는 과일을 셉니다. 그 후, 항상 보이는 과일이 가장 많은 칸으로 이동합니다 (이때, 가장 많은 과일을 가진 칸은 항상 유일합니다).

결국 Bessie는 (R, C) 위치에 도달하여 그곳의 파파야를 먹게 됩니다.

주어진 파파야 정글에서 Bessie가 (R, C) 위치의 파파야를 먹을 때까지 총 몇 개의 파파야를 먹는지 구하는 프로그램을 작성하세요.


입력

  • 첫 번째 줄: 두 개의 공백으로 구분된 정수 R과 C (1 \le R,C \le 40)

  • 두 번째 줄부터 R+1번째 줄까지: 각 줄마다 C개의 공백으로 구분된 정수 F_ij가 주어지며, 이는 각 칸에 있는 파파야의 개수를 나타냅니다. (1 \le F_ij\le 100)


출력

첫 번째 줄: Bessie가 (R, C) 위치에서 파파야를 먹을 때까지 먹은 파파야의 총 개수를 출력합니다.


예제1

입력
34
3345
4532
1742
출력
39
     (1,1) ---> (1,C)
(1,1) 3a  3   4g  5h  (1,C)
  |   4b  5c  3f  2i    |
(R,1) 1   7d  4e  2j  (R,C)
     (R,1) ---> (R,C)

위와 같이 알파벳 a로 표기된 곳부터 j로 표기된 위치까지 알파벳 순서대로 방문하면 총 39개의 파파야를 먹게된다.


태그

출처

USACO October 2009 Gold 4

역링크