/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は H 行 W 列のマス目で表される迷路を探索しています。
開始地点 S からゴール G へ辿り着く必要があります。
各マスには次のいずれかの文字が書かれています。
S: 開始地点（通行可能）G: ゴール（通行可能）O: 通常マス（通行可能、アルファベットの大文字オー）B: 壁（通行不可能）P: 罠マス（通行可能）
高橋君は最初 S のマスにおり、受けた累積ダメージは 0 です。
1 回の移動で、現在いるマスから上下左右に隣接するマスへ進むことができます。ただし、マス目の外や B のマスには進むことができません。同じマスを何度でも通ることができます。
移動先のマスが P であるとき、そのマスに入るたびに累積ダメージが 1 増えます。同じ P のマスであっても、入るたびにダメージは加算されます。S, G, O のマスに入ってもダメージは増えません。
高橋君が G のマスに到達した時点で、探索は即座に終了します。
S から G へ到達する経路が存在する場合、到達時の累積ダメージの最小値を出力してください。
どのように移動しても G に到達できない場合は -1 を出力してください。
制約
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- H \times W \leq 10^6
- H, W は整数である
- A_i \, (1 \leq i \leq H) は
S,G,O,B,Pからなる長さ W の文字列である - 入力全体にちょうど 1 個の
Sと、ちょうど 1 個のGが含まれる
入力
入力は以下の形式で標準入力から与えられる。
H W A_1 A_2 \vdots A_H
H, W は迷路の行数と列数を表す整数である。
A_i \, (1 \leq i \leq H) は長さ W の文字列であり、A_i の j 文字目 (1 \leq j \leq W) は上から i 行目、左から j 列目のマスの種類を表す。
出力
S から G へ到達するまでに受ける累積ダメージの最小値を 1 行で出力せよ。到達できない場合は -1 を出力せよ。
入力例 1
3 5 SPOOG BBBBO OOOOO
出力例 1
1
入力例 2
4 5 SOBBG OOBBB BBBBB POOOO
出力例 2
-1
入力例 3
8 10 SOOPBPOOOO BBOPBOBBBO OOOPOOPOOO OBBBBBBPOB OOPPPBOOOB BOBOPBOBPO OPOOPOOOPO BBBBOBBBPG
出力例 3
3
入力例 4
12 16 SPOOBPOOOOBOPPPO OBBOOPOBOOOOBOPO OPOPBOOOBBOPOOBO OOBOPPBOOOOPBOOO OPPOBOOOPBBBOOPO OBOPOOBOOOPOPBOO OOOOPBBBOBOOOPPO OPBBOOPOOOOBOBOO OOPOBBOOPPOOBBPO OBOPOOOPBOBOOOOO OPPBBOOOOPPOBPOO OOOOPOOOOPPOOOOG
出力例 4
1
入力例 5
1 2 SG
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi is exploring a maze represented by a grid with H rows and W columns.
He needs to reach the goal G from the starting point S.
Each square contains one of the following characters:
S: Starting point (passable)G: Goal (passable)O: Normal square (passable, uppercase letter O)B: Wall (impassable)P: Trap square (passable)
Takahashi starts on the S square with a cumulative damage of 0.
In one move, he can advance from his current square to an adjacent square in one of the four directions (up, down, left, right). However, he cannot move outside the grid or onto a B square. He may pass through the same square any number of times.
When the destination square is P, the cumulative damage increases by 1 each time he enters that square. Even for the same P square, damage is added every time he enters it. Entering S, G, or O squares does not increase the damage.
The exploration ends immediately when Takahashi reaches the G square.
If a path from S to G exists, output the minimum cumulative damage upon reaching the goal.
If it is impossible to reach G regardless of how he moves, output -1.
Constraints
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- H \times W \leq 10^6
- H, W are integers
- A_i \, (1 \leq i \leq H) is a string of length W consisting of
S,G,O,B,P - The entire input contains exactly one
Sand exactly oneG
Input
The input is given from standard input in the following format:
H W A_1 A_2 \vdots A_H
H, W are integers representing the number of rows and columns of the maze.
A_i \, (1 \leq i \leq H) is a string of length W, where the j-th character (1 \leq j \leq W) of A_i represents the type of the square at the i-th row from the top and the j-th column from the left.
Output
Output in one line the minimum cumulative damage received when traveling from S to G. If it is impossible to reach G, output -1.
Sample Input 1
3 5 SPOOG BBBBO OOOOO
Sample Output 1
1
Sample Input 2
4 5 SOBBG OOBBB BBBBB POOOO
Sample Output 2
-1
Sample Input 3
8 10 SOOPBPOOOO BBOPBOBBBO OOOPOOPOOO OBBBBBBPOB OOPPPBOOOB BOBOPBOBPO OPOOPOOOPO BBBBOBBBPG
Sample Output 3
3
Sample Input 4
12 16 SPOOBPOOOOBOPPPO OBBOOPOBOOOOBOPO OPOPBOOOBBOPOOBO OOBOPPBOOOOPBOOO OPPOBOOOPBBBOOPO OBOPOOBOOOPOPBOO OOOOPBBBOBOOOPPO OPBBOOPOOOOBOBOO OOPOBBOOPPOOBBPO OBOPOOOPBOBOOOOO OPPBBOOOOPPOBPOO OOOOPOOOOPPOOOOG
Sample Output 4
1
Sample Input 5
1 2 SG
Sample Output 5
0