11561 - Getting Gold

有一個文字介面的探險遊戲，玩家在迷宮中行走尋找寶物，同時避免掉進陷阱，遊戲在一個四方形的區域中進行，玩家對迷宮的環境所知有限。

玩家可在迷宮中上、下、左、右任意地行走，行經的路上有寶物就可以撿起來，若玩家所在的位置四週(上、下、左、右)有陷阱的話，可以感覺得到危險，但並不知道陷阱在哪個方向，也不知道四週有幾個陷阱。若試著要走到有牆壁的位置，玩家會發現牆壁無法前進而停留在原地。

本遊戲的目地是在保證安全的情況下取得最多的寶物。

Input

輸入有多組測試資料，每組資料的第一列有兩個正整數W與H，其值介於3~50之間，分別為迷宮的寬度與長度，接下來有H列，每列有W個字元組成該迷宮，每一個字元意義表示如下：

P	玩家一開始所在的位置
G	該位置有寶物
T	陷阱
#	牆面
.	一般的地板

一個地圖只會有一個 'P'，且地圖四週一定以牆避圍起來。

Output 

請每組測試資料輸出在不會有落入陷阱的風險的情況下，玩家最多可取得的寶物數量。

Sample Input 

7 4
#######
#P.GTG#
#..TGG#
#######
8 6
########
#...GTG#
#..PG.G#
#...G#G#
#..TG.G#
########

Sample Output 

1
4

---

原文出處