Prerequisite: 01-BFS

Consider how to solve the following problem.

You are given a (directed) graph in which every edge has a length of \(0\) or \(1\).
Find the shortest distance from Vertex \(S\) to each vertex on this graph.

Those who are ready to try Problem E of ABC probably know that this problem can be solved with algorithms of solving shortest path problem like Dijkstra’s algorithm. This time, we will introduce a more efficient way.
Let’s take a look at the details of 01-BFS.

• First, prepare an empty deque.
• Define provisional shortest distances \(D[\) vertex index \(]=\{\) provisional distance \(\}\) as follows.
  • \(D[S]=0\).
  • \(D[x]=\infty\) for every vertex \(x\) other than \(S\).
• Add vertex \(S\) as the only element of the deque.
• Repeat the following until deque becomes empty.
  • Pop one element from the head of the deque. Let \(V\) be the popped vertex.
  • If \(V\) has not been visited yet, do the following operation and mark \(V\) as visited.
    • For each vertex \(W\) adjacent to \(V\), do the following.
      • If the length of the edge connecting \(V\) and \(W\) is \(0\) and \(D[W]>D[V]\), then push \(W\) to the head of the deque and let \(D[W]=D[V]\).
      • If the length of the edge connecting \(V\) and \(W\) is \(1\) and \(D[W]>D[V]+1\), then push \(W\) to the tail of the deque and let \(D[W]=D[V]+1\).

While the outline of the algorithm is the same as Dijkstra’s algorithm, it is distinctive in the usage of the deque.
In this algorithm, the deque plays the role of priority_queue in Dijkstra’s algorithm. If the elements are popped from the deque in the increasing order of the distances, then the algorithm works; indeed, this algorithm does work.

Solution of this problem

Now let’s consider how to solve the original problem with 01-BFS.
Do 01-BFS on a graph in which the vertices are triplets \((\)the \(x\)-coordinate of the square, the \(y\)-coordinate of the square, the direction of the last move\()\).
If the direction of the last move and the next move are different, the number of moves increases by \(1\); if they are the same, it increases by \(0\).
Therefore, the problem has been boiled down to 01-BFS. The time complexity is \(O(N^2)\). (Since the execution time limit is relatively long, in fast languages you may use Dijkstra’s algorithm instead of 01-BFS, which costs \(O(N^2 \log N)\) time but still will be accepted.)

Sample code (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;
}