前知識: 01-bfs

以下の問題を解くことを考えてみましょう。

全ての辺の長さが \(0\) か \(1\) である ような(有向)グラフが与えられます。
このグラフの頂点 \(S\) から各頂点までの最短距離を求めてください。

ABCのE問題に挑む方であれば、この問題が dijkstra 法などの最短経路問題を解くアルゴリズムによって解けることはご存じかと思います。今回は、それよりも効率的な解法を紹介します。
早速、 01-bfs とは何かを具体的に見ていきましょう。

• まず、空の deque を用意する。
• 暫定的な最短距離 \(D[\) 頂点番号 \(]=\{\) 暫定距離 \(\}\) を以下のように定義する。
  • \(D[S]=0\)
  • \(S\) 以外の頂点 \(x\) について、 \(D[x]=\infty\)
• deque の唯一の要素として、頂点 \(S\) を入れる。
• deque が空になるまで、以下を繰り返す。
  • deque の先頭から要素をひとつ取り出し、これを頂点 \(V\) とする。
  • \(V\) が未探索であれば、以下の操作を行った上で \(V\) を探索済みとする。
    • \(V\) に隣接する全ての頂点 \(W\) について、以下を行う。
      • もし \(V\) と \(W\) を結ぶ辺の長さが \(0\) であり、 \(D[W]>D[V]\) であれば、 deque の先頭に \(W\) を入れて、 \(D[W]=D[V]\) とする。
      • もし \(V\) と \(W\) を結ぶ辺の長さが \(1\) であり、 \(D[W]>D[V]+1\) であれば、 deque の末尾に \(W\) を入れて \(D[W]=D[V]+1\) とする。

大まかな流れは dijkstra 法と同じですが、特徴的なのは deque の操作です。
dijkstra 法の priority_queue の役割を deque が担っているような流れになっているので、 deque から要素を取り出すときにそれが距離の昇順になっていればこのアルゴリズムは上手くいき、実際にこのアルゴリズムは上手くいきます。

本問題の解法

では、本問題を 01-bfs で解いてみましょう。
\((\) マスの \(x\) 座標 , マスの \(y\) 座標 , 直前の移動方向 \()\) という情報の \(3\) つ組を \(1\) つの頂点として 01-bfs を行います。
このとき、直前の移動方向と変化があれば必要手数が \(1\) 手増加し、変化がなければ直前の遷移と同じ手で移動できるので必要手数が \(0\) 手増加します。
よって、本問題を 01-bfs に帰着することができました。
計算量は \(O(N^2)\) です。(ただし、実行時間制限に余裕があるので高速な言語であれば 01-bfs の部分を dijkstra 法として実装する \(O(N^2 \log N)\) でも正答可能です。)

実装例(C++):

#include<bits/stdc++.h>

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

int dx[4]={-1,-1,1,1};
int dy[4]={-1,1,-1,1};

int main(){
  int n,ax,ay,bx,by;
  cin >> n >> ax >> ay >> bx >> by;
  ax--;ay--;bx--;by--;
  vector<string> s(n);
  for(auto &nx : s){cin >> nx;}

  vector<vector<vector<int>>> d(n,vector<vector<int>>(n,vector<int>(4,1e9)));
  vector<vector<vector<bool>>> fl(n,vector<vector<bool>>(n,vector<bool>(4,false)));

  deque<ppi> dq;
  for(int i=0;i<4;i++){
    int cx=ax+dx[i];
    int cy=ay+dy[i];
    if(!(0<=cx && cx<n)){continue;}
    if(!(0<=cy && cy<n)){continue;}
    if(s[cx][cy]=='#'){continue;}
    d[cx][cy][i]=1;
    dq.push_back({{cx,cy},i});
  }

  while(!dq.empty()){
    ppi od=dq.front();dq.pop_front();
    if(od.first==make_pair(bx,by)){
      cout << d[bx][by][od.second] << '\n';
      return 0;
    }
    int cx=od.first.first;
    int cy=od.first.second;
    if(fl[cx][cy][od.second]){continue;}
    fl[cx][cy][od.second]=true;
    int cd=d[cx][cy][od.second];

    for(int i=0;i<4;i++){
      int nx=cx+dx[i];
      int ny=cy+dy[i];
      if(!(0<=nx && nx<n)){continue;}
      if(!(0<=ny && ny<n)){continue;}
      if(s[nx][ny]=='#'){continue;}

      int nd=cd;
      if(i!=od.second){nd++;}
      if(d[nx][ny][i]>nd){
        d[nx][ny][i]=nd;
        if(i==od.second){dq.push_front({{nx,ny},i});}
        else{dq.push_back({{nx,ny},i});}
      }
    }
  }
  cout << "-1\n";
  return 0;
}