写作业偶遇 TLE，拼尽全力无法战胜。

题目链接

题意简述：给定一个 $n \times m$ 的棋盘，有一些 X 点不能经过，求一个皇后从 S 点到 T 点所需要的最小步数。即使皇后是从 X 点上面飞过去也不行。

思路是拐弯代价为 $1$，不拐弯代价为 $0$，然后 01bfs。

代码：

#include <tuple>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <algorithm>

using namespace std;

bool km[1005][1005];
int dst[1005][1005][8];
constexpr int dx[8] = { 0, 0, 1, 1, 1, -1, -1, -1 };
constexpr int dy[8] = { 1, -1, 0, 1, -1, 0, 1, -1 };

// 由于 deque 实在是太垃圾了，我们这里实现一个双端队列。
template<typename T>
class dedequeue
{
protected:
    class linknode
    {
    public:
        linknode* prev, * next;
        T val;
    };
private:
    linknode* _vend;
    int _sz;
public:
    dedequeue()
    {
        _vend = new linknode;
        _vend->prev = _vend->next = _vend;
        _sz = 0;
    }
    void push_front(T x)
    {
        linknode* newnode = new linknode;
        newnode->val = x;
        newnode->prev = _vend;
        newnode->next = _vend->next;
        _vend->next->prev = newnode;
        _vend->next = newnode;
        _sz++;
    }
    void push_back(T x)
    {
        linknode* newnode = new linknode;
        newnode->val = x;
        newnode->next = _vend;
        newnode->prev = _vend->prev;
        _vend->prev->next = newnode;
        _vend->prev = newnode;
        _sz++;
    }
    bool pop_back()
    {
        if (!_sz) return false;
        linknode* todelete = _vend->prev;
        _vend->prev = todelete->prev;
        todelete->prev->next = _vend;
        _sz--;
        return true;
    }
    bool pop_front()
    {
        if (!_sz) return false;
        linknode* todelete = _vend->next;
        _vend->next = todelete->next;
        todelete->next->prev = _vend;
        _sz--;
        return true;
    }
    T front()
    {
        return _vend->next->val;
    }
    T back()
    {
        return _vend->prev->val;
    }
    size_t size() { return _sz; }
    bool empty() { return size() == 0; }
    ~dedequeue()
    {
        while (pop_back());
        delete _vend;
    }
};

void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int sx, sy, tx, ty;
    for (int i = 1; i <= n; i++)
    {
        memset(dst[i], 0x3f, sizeof dst[i]);
        while (getchar() != '\n');
        for (int j = 1; j <= m; j++)
        {
            char ch = getchar();
            km[i][j] = (ch != 'X');
            if (ch == 'S')
            {
                sx = i;
                sy = j;
            }
            if (ch == 'F')
            {
                tx = i;
                ty = j;
            }
        }
    }
    memset(dst[sx][sy], 0, sizeof dst[sx][sy]);
    dedequeue<tuple<int, int, int>> q;
    q.push_back({ sx, sy, 0 });
    q.push_back({ sx, sy, 1 });
    q.push_back({ sx, sy, 2 });
    q.push_back({ sx, sy, 3 });
    q.push_back({ sx, sy, 4 });
    q.push_back({ sx, sy, 5 });
    q.push_back({ sx, sy, 6 });
    q.push_back({ sx, sy, 7 });
    // 感觉你的代码不简洁
    // 不简洁个【小粉兔】啊
    while (!q.empty())
    {
        tuple<int, int, int> u = q.front();
        q.pop_front();
        int ux = get<0>(u), uy = get<1>(u);
        for (int i = 0; i < 8; i++)
        {
            int vx = ux + dx[i], vy = uy + dy[i];
            if (vx < 1 || vx > n || vy < 1 || vy > m)
                continue;
            if (!km[vx][vy]) continue;
            int distadd = (i != get<2>(u));
            if (dst[ux][uy][get<2>(u)] + 1 < dst[vx][vy][i])
            {
                dst[vx][vy][i] = 
                    dst[ux][uy][get<2>(u)] + distadd;
                if (distadd) q.push_back({ vx, vy, i });
                else q.push_front({ vx, vy, i });
            }
        }
    }
    int k = min({
        dst[tx][ty][0], dst[tx][ty][1], dst[tx][ty][2],
        dst[tx][ty][3], dst[tx][ty][4], dst[tx][ty][5],
        dst[tx][ty][6], dst[tx][ty][7]
        });
    if (k == 0x3f3f3f3f) printf("-1\n");
    else printf("%d\n", k);
}


int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}
/*
        ________            __________     
       / ______ \          / ________ \    
      / /      \ \        / /        \ \   
     / /        \ \      /_/          \ \  
    / /          \ \                  | |  
   / /            \ \               _/ /   
  | |              | |           __/ _/    
   \ \            / /          _/ __/      
    \ \          / /        __/ _/         
     \ \        / /        / __/           
      \ \______/ /        / /___________   
       \________/        /______________|  
*/