21772번 - 가희의 고구마 먹방 출처

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

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

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

• 가희는 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개 이상 있습니다.
• 가희는 장애물을 뛰어 넘거나 통과할 수 없습니다.
• 가희는 맵 밖으로 나갈 수 없습니다.