2384. Getting Gold

单点时限: 5.0 sec

内存限制: 256 MB

We’re building an old-school back-to-basics computer game. It’s a very simple text based adventure game where you walk around and try to nd treasure, avoiding falling into traps. The game is played on a rectangular grid and the player gets very limited information about her surroundings.

The game will consist of the player moving around on the grid for as long as she likes (or until she falls into a trap). The player can move up, down, left and right (but not diagonally). She will pick up gold if she walks into the same square as the gold is. If the player stands next to (i.e., immediately up, down, left, or right of) one or more traps, she will “sense a draft” but will not know from what direction the draft comes, or how many traps she’s near. If she tries to walk into a square containing a wall, she will notice that there is a wall in that direction and remain in the position where she was.

For scoring purposes, we want to show the player how much gold she could have gotten safely. That is, how much gold can a player get playing with an optimal strategy and always being sure that the square she walked into was safe. The player does not have access to the map and the maps are randomly generated for each game so she has no previous knowledge of the game.

输入格式

The first line of input contains two positive integers W and H, neither of them smaller than 3 or larger than 50, giving the width and the height of the map,respectively. The next H lines contain W characters each, giving the map. The symbols that may occur in a map are as follows:

P — the player’s starting position

G — a piece of gold

T — a trap

— a wall

. — normal floor

There will be exactly one ‘P’ in the map, and the border of the map will always contain walls.

输出格式

Output the number of pieces of gold the player can get without risking falling into a trap.

样例

Input
7 4
#######
#P.GTG#
#..TGG#
#######
/*
8 6
########
#...GTG#
#..PG.G#
#...G#G#
#..TG.G#
########
*/
Output
1
/*
4
*/

7 人解决,11 人已尝试。

8 份提交通过,共有 16 份提交。

6.6 EMB 奖励。

创建: 12 年,11 月前.

修改: 4 年前.

最后提交: 10 月前.

来源: NCPC 2008

题目标签