(Analysis by Nick Wu)

We start by solving a simpler problem - given a specific starting location and orientation, compute the minimum distance needed for Bessie to reach some other square. In this situation, we can do a breadth-first search through the grid, keeping track of Bessie's location and direction. Note that this graph has at most $4N^2$ vertices, and each vertex has at most $3$ edges.

The given problem is more complicated though - Bessie could be in one of two orientations, and we don't know which one she's in. We need to make sure that, no matter which orientation she is in, she gets to the final destination.

Fortunately, we can turn this problem back into a standard shortest path problem solvable by breadth-first search, only in a much larger graph. Since Bessie's "state" can be represented by the (position, direction) of two possible situations in which she can find herself in at a given point in time, we end up with $16N^4$ possible states, each a vertex in a large graph through which we will conduct our breadth-first search. Since each vertex still has at most three outgoing edges (corresponding to the transitions caused by "forward", "turn left", and "turn right"), the graph is still small enough that our breadth-first search will run quickly.

import java.io.*;
import java.util.*;
public class cownav {
static int[] dx = new int[]{-1,0,1,0};
static int[] dy = new int[]{0,1,0,-1};
static int n;
static char[][] grid;
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("cownav.out")));
grid = new char[n][];
for(int i = 0; i < n; i++) {
}
int[][][][][][] dp = new int[n][n][4][n][n][4];
dp[n-1][0][0][n-1][0][1] = 1;
q.add(new State(n-1, 0, 0, n-1, 0, 1));
while(!q.isEmpty()) {
State curr = q.removeFirst();
if(curr.ax == 0 && curr.bx == 0 && curr.ay == n-1 && curr.by == n-1) {
break;
}
for(State next: curr.genTransitions()) {
if(dp[next.ax][next.ay][next.ad][next.bx][next.by][next.bd] == 0) {
}
}
}
pw.close();
}
static class State {
int ax, ay, ad;
int bx, by, bd;
public State(int ax, int ay, int ad, int bx, int by, int bd) {
this.ax = ax;
this.ay = ay;
this.bx = bx;
this.by = by;
this.bd = bd;
}
public State[] genTransitions() {
return new State[]{
turnLeft(),
turnRight(),
};
}
private State turnLeft() {
return new State(ax, ay, (ad+3)%4, bx, by, (bd+3)%4);
}
private State turnRight() {
return new State(ax, ay, (ad+1)%4, bx, by, (bd+1)%4);
}
private State advance() {
int nax = ax;
int nay = ay;
if(nax != 0 || nay != n-1) {
if(nax + dx[ad] >= 0 && nax + dx[ad] < n) {
}
if(nay + dy[ad] >= 0 && nay + dy[ad] < n) {
}
if(grid[nax][nay] == 'H') {
nax = ax;
nay = ay;
}
}
int nbx = bx;
int nby = by;
if(nbx != 0 || nby != n-1) {
if(nbx + dx[bd] >= 0 && nbx + dx[bd] < n) {
nbx += dx[bd];
}
if(nby + dy[bd] >= 0 && nby + dy[bd] < n) {
nby += dy[bd];
}
if(grid[nbx][nby] == 'H') {
nbx = bx;
nby = by;
}
}
return new State(nax, nay, ad, nbx, nby, bd);
}
}
}