@shinzanmono

思路分析

本该是一道BFS裸题，但是由于有各种细节，所以并不太好一次过呢。

和裸BFS不同的地方主要在于：

1. 别的障碍物一般就设置在机器人的路径上，但这题是在格子上，机器人走的是格子线，所以判别障碍物的形式就要发生改变。
2. 别的机器人一次走一格，但这题机器人一次可以走三格。这意味着如果它要走三格，那么路径上都必须不能有障碍物。
3. 机器人可以转向，而且转向也要花时间

对于第一点，我们读入地图的时候，让i,j从0开始，当作地图小方块左上角的坐标，那么地图范围是$(0, 0)\sim(n, m)$。机器人可以走的范围是$(1, 1)\sim(n-1, m-1)$（不能撞墙啊）。

对于障碍物的判别方式（如下图），假设我们现在要到黑色点去，那么红色点的 地方必不能有障碍物。四个方向的判别方式有一些微小的差别，所以可以额外开一个数组来记录偏移量（对应我的代码中的dx1,dy1和dx2,dy2）。

对于第二点，我们依次尝试从某点迈出一、二、三步，如果在某一步已经不能走了，那么之后的都不能成为可行结点了。

对于第三点，我们可以在迈出这一步之前，把转向所需的时间先加上。先利用一个cost[N][N][4]来记录时间，那么cost[x][y][ori]含义是在(x,y)点，从起点到面向某方向ori所需要的时间。第三维0,1,2,3分别表示N、E、S、W。例如机器人现在面向N，那么先在W和E两个方向上加1，再在S上加2，即代码中的：

int oris[] = { top.ori, (top.ori + 1) & 3, (top.ori + 3) & 3, (top.ori + 2) & 3 };
cond_assign(cost[top.x][top.y][oris[1]], cost[top.x][top.y][top.ori] + 1);
cond_assign(cost[top.x][top.y][oris[2]], cost[top.x][top.y][top.ori] + 1);
cond_assign(cost[top.x][top.y][oris[3]], cost[top.x][top.y][top.ori] + 2);

cond_assign这个函数是只有这个位置这个方向没有被访问过时才进行赋值。

加上方向之后，再按照时间依次讨论每个方向的前进即可。这样一来，就可以在样例跑出13的错解了。

重点

我说的这么有道理，问题出在哪了？当用这个思路在样例上跑，会发现它竟然搜到了绿色的路径。如果不考虑转向的话，绿色路径确实会先于红色路径搜到，这是因为红色用了7步，而绿色用了6步，所以按照深度来说，当然是绿色的先被搜到。

问题在于，完全转向（例如面朝N转到S）再前进，应该严格后于直接前进加入到队列中。因为前者要花3秒，后者只需要1秒。这个好办，我按照oris数组（这个数组的顺序是直面、左转一次、右转一次、左转两次）的值来遍历不就好了吗？

但这样还是不够，因为直接前进再转向一次也只要两秒，而完全转向再前进要三秒，也就是说我得让前者先于后者被加入队列。为了解决这个问题，考虑使用优先队列。在state中除了保存x,y,ori，再加一个时间戳t（其实就是cost[x][y][ori]），每次取出时间戳最靠前的那个就可以了。由于大致是有序的，所以堆的调整开销相当小，可以放心使用。

细节处理

可能没有AC就是漏了这些小细节吧...

1. 机器人有可能一开始就在障碍物上，或者终点在障碍物里，这个时候直接输出-1。
2. 如果起点和终点重合，那就不用走了，直接输出0。

AC 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 60;
bool mp[N][N];
int cost[N][N][4];
int n, m;

struct state {
    int t, x, y;
    int ori; // orientation
    bool operator>(const state& s) const {
        return t > s.t;
    }
};
bool check(int x, int y) {
    if (x < 0 || y < 0)
        return false;
    if (x >= n || y >= m)
        return false;
    return true;
}
void cond_assign(int& dst, int v) {
    if (dst == -1) // 没有探索过才赋值
        dst = v;
}
int sx, sy, ex, ey;
int dx[] = { -1, 0, 1, 0 }, dx1[] = { -1, 0, 0, 0 }, dx2[] = { -1, -1, 0, -1 };
int dy[] = { 0, 1, 0, -1 }, dy1[] = { 0, 0, 0, -1 }, dy2[] = { -1, 0, -1, -1 };
int ori;
int bfs() {
    priority_queue<state, vector<state>, greater<state>> q;
    cost[sx][sy][ori] = 0;
    q.emplace(0, sx, sy, ori);
    while (q.size()) {
        auto top = q.top();
        q.pop();
        int oris[] = { top.ori, (top.ori + 1) & 3, (top.ori + 3) & 3, (top.ori + 2) & 3 };
        cond_assign(cost[top.x][top.y][oris[1]], cost[top.x][top.y][top.ori] + 1);
        cond_assign(cost[top.x][top.y][oris[2]], cost[top.x][top.y][top.ori] + 1);
        cond_assign(cost[top.x][top.y][oris[3]], cost[top.x][top.y][top.ori] + 2);

        for (int i : oris) // 根据顺序遍历，其实用了优先队列之后也就不需要了
            for (int j = 1; j <= 3; ++j) {
                int x = top.x + dx[i] * j, y = top.y + dy[i] * j;
                if (!check(x, y) || x == 0 || y == 0) // 不可以越界
                    break;
                if (check(x + dx1[i], y + dy1[i]) && mp[x + dx1[i]][y + dy1[i]]) //不可以有障碍物
                    break;
                if (check(x + dx2[i], y + dy2[i]) && mp[x + dx2[i]][y + dy2[i]]) //不可以有障碍物
                    break;
                if (cost[x][y][i] != -1) // 已经去过了
                    continue;
                cost[x][y][i] = cost[top.x][top.y][i] + 1;
                if (x == ex && y == ey)
                    return cost[x][y][i];
                q.emplace(cost[x][y][i], x, y, i);
            }
    }
    return -1;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    memset(cost, -1, sizeof cost);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            cin >> mp[i][j];
    }

    cin >> sx >> sy >> ex >> ey;
    char ch;
    cin >> ch;
    if (ch == 'N')
        ori = 0;
    else if (ch == 'E')
        ori = 1;
    else if (ch == 'S')
        ori = 2;
    else
        ori = 3;
    if (sx == ex && sy == ey)
        cout << 0;
    else if (mp[sx][sy] | mp[ex][ey])
        cout << -1;
    else
        cout << bfs();
}