시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 431 112 86 26.791%

문제

가희는 고구마를 정말 좋아합니다.

이번에도 어김 없이 고구마 냄새가 났는데, 고구마가 보이지 않습니다. 오빠가 방 안에 고구마를 숨겨 놓았기 때문입니다.

오빠는 가희에게 하나의 게임을 제안하고, 게임의 규칙을 설명해 주었습니다. 게임 규칙은 아래와 같습니다.

  • 가희는 1초마다 상하좌우 방향 중 한 방향으로 1번 이동하거나, 이동하지 않고 그 자리에 머무를 수 있습니다.
  • 가희가 이동한 지점에 고구마가 있는 경우에는, 고구마를 먹습니다. 고구마를 먹는 데 걸리는 시간은 없다고 가정합니다.
  • 가희가 고구마를 먹으면, 고구마가 다시 그 자리에 생기지 않습니다.

가희는 현재 위치에서 T초만큼 이동했을 때 고구마를 최대한 많이 먹고 싶습니다. 가희가 최대 몇 개의 고구마를 먹을 수 있는지 알려주세요.

입력

첫 번째 줄에 맵의 세로 크기 R, 가로 크기 C, 가희가 이동하는 시간 T가 주어집니다.

두 번째 줄부터 R+1번째 줄까지 길이가 C인 문자열이 주어집니다.

주어지는 문자열에 있는 문자는 가희를 나타내는 'G', 고구마를 나타내는 'S', 빈 칸을 나타내는 '.', 장애물을 나타내는 '#' 중 하나 입니다.

출력

문제에 대한 답을 출력합니다.

제한

  • 2 ≤ R ≤ 100
  • 2 ≤ C ≤ 100
  • 1 ≤ T ≤ 10
  • 가희를 나타내는 문자인 'G'는 맵 안에 하나만 있습니다. 'G'가 있는 위치는, 가희의 현재 위치입니다.
  • 'S'가 있는 위치에 고구마는 1개 있습니다.
  • 고구마와 장애물은 최소 1개 이상 있습니다.
  • 가희는 장애물을 뛰어 넘거나 통과할 수 없습니다.
  • 가희는 맵 밖으로 나갈 수 없습니다.

예제 입력 1

11 11 5
........G..
......S.#S.
........#.S
...........
...........
.##########
.##########
...........
...........
##########.
...........

예제 출력 1

2

답이 될 수 있는 경우 중 하나는 아래와 같습니다.

[그림] 고구마를 2개 먹을 수 있는 경로 중 하나

예제 입력 2

11 11 5
G....S.....
...........
...........
...........
...........
...........
.....#.....
...........
...........
...........
...........

예제 출력 2

1

가희가 현재 있는 위치로부터 5번 이동하는 것이 고구마를 제일 많이 먹을 수 있는 방법입니다.

출처

Contest > 가희와 함께 하는 코딩 테스트 > 가희와 함께 하는 1회 코딩 테스트 2번