금 모으기

옛날 감성의 단순한 텍스트 기반 모험 게임을 만든다. 플레이어는 격자 위를 돌아다니며 함정을 피해 보물(금)을 모은다.

게임은 직사각형 격자에서 진행되며, 플레이어는 자신의 주변에 대해 매우 제한된 정보만 얻는다. 플레이어는 위·아래·왼쪽·오른쪽으로만 이동할 수 있고(대각선 이동은 불가), 원하는 만큼 계속 이동할 수 있다. 단, 함정에 빠지면 게임이 끝난다.

• 금이 있는 칸에 들어가면 그 금을 줍는다.
• 함정과 바로 인접한(위·아래·왼쪽·오른쪽) 칸에 서 있으면 "바람을 느낀다". 그러나 바람이 어느 방향에서 오는지, 근처에 함정이 몇 개인지는 알 수 없다.
• 벽이 있는 칸으로 들어가려 하면 그 방향에 벽이 있음을 알아채고 원래 자리에 그대로 머문다.

점수 계산을 위해, 플레이어가 들어가는 칸이 항상 안전하다고 확신할 수 있는 상태에서 최적으로 움직였을 때 모을 수 있는 금의 개수를 알고 싶다. 지도는 매번 무작위로 생성되어 플레이어가 미리 알 수 없으므로, 지도에 대한 사전 지식은 전혀 없다.

첫째 줄에 지도의 너비 W와 높이 H가 주어진다 ($3 \le W, H \le 50$). 다음 H개의 줄에는 각각 W개의 문자로 이루어진 지도가 주어진다. 사용되는 기호는 다음과 같다.

• P — 플레이어의 시작 위치
• G — 금 한 덩이
• T — 함정
• # — 벽
• . — 일반 바닥

P는 지도에 정확히 하나 있으며, 지도의 테두리는 항상 벽으로 되어 있다.

플레이어가 함정에 빠질 위험 없이 안전하게 모을 수 있는 금의 개수를 출력한다.