Description

Bessie has gotten herself stuck on the wrong side of Farmer John ‘s barn again, and since her vision is so poor, she needs your help navigating across the barn. The barn is described by an \(n \times n\) grid of square cells (\(2 \leq n \leq 20\)) , some being empty and some containing impassable haybales. Bessie starts in the lower-left corner (cell \((1, 1)\)) and wants to move to the upper-right corner (cell \((n, n)\)) . You can guide her by telling her a sequence of instructions, each of which is either “forward”“,” turn left 90 degrees “”, or “turn right 90 degrees”“. You want to issue the shortest sequence of instructions that will guide her to her destination. If you instruct Bessie to move off the grid (i. e., into the barn wall) or into a haybale, she will not move and will skip to the next command in your sequence. Unfortunately, Bessie doesn’ t know if she starts out facing up (towards cell \((1, 2)\)) or right (towards cell \((2, 1)\)) . You need to give the shortest sequence of directions that will guide her to the goal regardless of which case is true. Once she reaches the goal she will ignore further commands.

给定一个 \(n \times n\) 的网格 \((n \leq 20)\), 你从左下角出发, 要到达右上角, 网格中会有障碍物你要给定一个长度最短的行为序列 (往前走, 左转, 右转), 使得无论 Bessie 处于左下角时是头朝向上还是朝向左都可以在执行完这个序列后到达右上角. 如果当前的行为会导致 Bessie 走到障碍物上或者越界, 则 Bessie 会忽视这个行为.

Input

The first line of input contains \(n\).

第一行为 \(n\) 表示网格大小;

Each of the \(n\) following lines contains a string of exactly \(n\) characters, representing the barn. The first character of the last line is cell \((1, 1)\). The last character of the first line is cell \((n, n)\). Each character will either be an H to represent a haybale or an E to represent an empty square.

接下来 \(n\) 行每行 \(n\) 列, 描述这个网格,H 表示障碍物,E 表示空地;

It is guaranteed that cells \((1, 1)\) and \((n, n)\) will be empty, and furthermore it is guaranteed that there is a path of empty squares from cell \((1, 1)\) to cell \((n, n)\)

数据保证左下角和右上角一定是空地, 且一定有解.

Output

On a single line of output, output the length of the shortest sequence of directions that will guide Bessie to the goal, irrespective whether she starts facing up or right.

输出一个整数, 代表最短命令序列的长度.

Sample Input

3
EHE
EEE
EEE

Sample Output

9

Explanation

Bessie 首先开始的时候不知道是朝左还是朝右. 所以我们需要将状态拆成两部分, 一部分是 最开始朝左, 另一部分是最开始朝右的状态. 这样我们才可以在命令转移的时候考虑到两种 不同的情况对应的位置.

然后针对每一种情况特判一下就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 25;
const int infinit = 0x3fffffff;

int n, arr[maxn][maxn];
int dist[maxn][maxn][maxn][maxn][4][4];
bool vis[maxn][maxn][maxn][maxn][4][4];

const int movx[4] = { -1, 0, 1,  0 },
          movy[4] = {  0, 1, 0, -1 };

struct status {
    int x1, y1, x2, y2, d1, d2;
    status(int _1, int _2, int _3, int _4, int _5, int _6) {
        x1 = _1, y1 = _2, x2 = _3, y2 = _4, d1 = _5, d2 = _6; }
    status(void) {
        x1 = y1 = x2 = y2 = d1 = d2 = 0; }
};

bool accessible(int x, int y)
{
    if (x < 1 || x > n)
        return false;
    if (y < 1 || y > n)
        return false;
    if (!arr[x][y])
        return false;
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    rep(i, 1, n) rep(j, 1, n) {
        char c = '\0';
        while (c != 'E' && c != 'H') c = getchar();
        arr[i][j] = c == 'E';
    }
    // Finished input data procedures.
    // Clearing relax datum
    rep(x1, 0, n) rep(y1, 0, n) rep(x2, 0, n) rep(y2, 0, n)
        rep(d1, 0, 3) rep(d2, 0, 3)
            dist[x1][y1][x2][y2][d1][d2] = infinit,
            vis[x1][y1][x2][y2][d1][d2] = false;
    // Now trying SaaS (SPFA-as-a-Service, XD)
    queue<status> que;
    que.push(status(n, 1, n, 1, 0, 1));
    dist[n][1][n][1][0][1] = 0;
    vis[n][1][n][1][0][1] = true;
    while (!que.empty()) {
        status s = que.front();
        que.pop();
        int nx1 = s.x1 + movx[s.d1],
            ny1 = s.y1 + movy[s.d1];
        int nx2 = s.x2 + movx[s.d2],
            ny2 = s.y2 + movy[s.d2];
        // If not accessible, revert to previous configuration
        if (!accessible(nx1, ny1))
            nx1 = s.x1, ny1 = s.y1;
        if (!accessible(nx2, ny2))
            nx2 = s.x2, ny2 = s.y2;
        // Target approached, ignoring further movements
        if (s.x1 == 1 && s.y1 == n)
            nx1 = 1, ny1 = n;
        if (s.x2 == 1 && s.y2 == n)
            nx2 = 1, ny2 = n;
        // Setting macros for updating new locations
        #define old_loc(_arr) _arr[s.x1][s.y1][s.x2][s.y2][s.d1][s.d2]
        #define new_loc(_arr) _arr[nx1][ny1][nx2][ny2][s.d1][s.d2]
        #define rot_loc(_arr) _arr[s.x1][s.y1][s.x2][s.y2][nd1][nd2]
        // Relaxing new location
        if (old_loc(dist) + 1 < new_loc(dist)) {
            new_loc(dist) = old_loc(dist) + 1;
            if (!new_loc(vis)) {
                new_loc(vis) = true;
                que.push(status(nx1, ny1, nx2, ny2, s.d1, s.d2));
            }
        }
        // Relaxing from counter-clockwise rotation
        int nd1, nd2;
        nd1 = s.d1 - 1, nd2 = s.d2 - 1;
        if (nd1 < 0) nd1 = 3; if (nd2 < 0) nd2 = 3;
        if (old_loc(dist) + 1 < rot_loc(dist)) {
            rot_loc(dist) = old_loc(dist) + 1;
            if (!rot_loc(vis)) {
                rot_loc(vis) = true;
                que.push(status(s.x1, s.y1, s.x2, s.y2, nd1, nd2));
            }
        }
        // Relaxing from clockwise rotation
        nd1 = s.d1 + 1, nd2 = s.d2 + 1;
        if (nd1 > 3) nd1 = 0; if (nd2 > 3) nd2 = 0;
        if (old_loc(dist) + 1 < rot_loc(dist)) {
            rot_loc(dist) = old_loc(dist) + 1;
            if (!rot_loc(vis)) {
                rot_loc(vis) = true;
                que.push(status(s.x1, s.y1, s.x2, s.y2, nd1, nd2));
            }
        }
        // Finialized relaxation operations
        continue;
    }
    // Retrieving results
    int res = infinit;
    rep(d1, 0, 3) rep(d2, 0, 3)
        res = min(res, dist[1][n][1][n][d1][d2]);
    printf("%d\n", res);
    return 0;
}