srand   1년 전

문제

Jonas는 전설적인 황금 도시 엘도라도에 관한 컴퓨터 게임을 하고 있습니다.
Jonas는 황금 도시에서 무엇을 할까요? 당연히 황금을 모읍니다!

도시 지도는 $N \times M$ 크기의 직사각형이며, 각 칸에는 건물, 도로 또는 황금 동전이 있습니다.
Jonas는 남쪽(지도상 아래쪽)과 동쪽(지도상 오른쪽) 방향으로만 이동할 수 있으며, 가능한 한 많은 동전을 모으고 싶어 합니다.

Jonas가 서 있는 칸을 $(i, j)$라고 합시다:

  • 만약 칸 $(i, j)$에 황금 동전이 있다면, Jonas가 그것을 가져갑니다.

  • Jonas는 칸 $(i+1, j)$ 또는 $(i, j+1)$으로 이동할 수 있는데, 이 칸들이 지도 내에 존재하고 건물이 없어야 합니다.

  • 만약 더 이상 이동할 수 없으면 게임은 종료됩니다.

Jonas는 도시 지도를 모두 알고 있습니다.
그가 (1, 1) 칸에서 게임을 시작할 때, Jonas가 모을 수 있는 최대 동전 개수를 구하세요.

입력

첫 번째 줄에 도시 크기 $N$과 $M$이 주어집니다.

다음 $N$개의 줄에는 각 줄마다 $M$개의 문자 $s_{i,j}$가 주어집니다 ($1 \le i \le N$, $1 \le j \le M$):

  • 만약 $s_{i,j} = .$ 이면, 해당 칸에는 도로가 있습니다.

  • 만약 $s_{i,j} = x$ 이면, 해당 칸에는 건물이 있습니다.

  • 만약 $s_{i,j} = o$ 이면, 해당 칸에는 도로가 있고 그 위에 황금 동전이 놓여 있습니다.

지도 왼쪽 위 칸 $(1, 1)$에는 절대 건물이 없습니다.

출력

Jonas가 모을 수 있는 최대 황금 동전의 개수를 출력하세요.

sinderella   1년 전

변역 감사합니다.

댓글을 작성하려면 로그인해야 합니다.