本問題は、以下の形の最短経路問題です。

• P へと向かう通行可能な辺の長さは \(1\)
• それ以外の通行可能な辺の長さは \(0\)

このままダイクストラ法を適用するなどしでも解けますが、 01BFS と呼ばれる方法を紹介します。
これは、辺の長さが \(0\) と \(1\) のみであることを利用してダイクストラ法などで付く \(\log\) を計算量から落とすテクニックです。

• ダイクストラ法での priority_queue の代わりに、 deque(デック) \(dq\) を利用する。
• 長さ \(0\) の辺を通って頂点を発見した場合、 \(dq\) の先頭に追加する。
• 長さ \(1\) の辺を通って頂点を発見した場合、 \(dq\) の末尾に追加する。

こうすることで、 priority_queue に頼らずとも \(dq\) の中身を常に距離順にして距離順にマスを調べることができます。

本解法の時間計算量は \(O(HW)\) です。

Tips: なお、辺の長さが \(0,1,\dots,k\) のみであって \(k\) がある程度小さい時にも \(\log\) を落とすことができます。 1-K BFS や Dial’s algorithm として知られます。勘の良い方であれば方法を思いつけるかもしれないので、是非考えてみてください。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int dx4[4]={0,0,-1,1};
int dy4[4]={-1,1,0,0};

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> A(H);
  vector<vector<int>> d(H,vector<int>(W,1e9));
  vector<vector<int>> fl(H,vector<int>(W,0));
  deque<pi> dq;
  for(int i=0;i<H;i++){
    cin >> A[i];
    for(int j=0;j<W;j++){
      if(A[i][j]=='S'){
        dq.push_front({i,j});
        d[i][j]=0;
      }
    }
  }
  while(!dq.empty()){
    auto [x,y]=dq.front(); dq.pop_front();
    if(A[x][y]=='G'){
      cout << d[x][y] << "\n";
      return 0;
    }
    if(fl[x][y]){continue;}
    fl[x][y]=1;
    for(int k=0;k<4;k++){
      int nx=x+dx4[k];
      int ny=y+dy4[k];
      if(!(0<=nx && nx<H)){continue;}
      if(!(0<=ny && ny<W)){continue;}
      if(A[nx][ny]=='B'){continue;}
      if(A[nx][ny]=='P'){
        if(d[nx][ny]>d[x][y]+1){
          d[nx][ny]=d[x][y]+1;
          dq.push_back({nx,ny});
        }
      }
      else{
        if(d[nx][ny]>d[x][y]){
          d[nx][ny]=d[x][y];
          dq.push_front({nx,ny});
        }
      }
    }
  }
  cout << "-1\n";
  return 0;
}