罗密欧与朱丽叶身处一个 m × n 的迷宫中

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

// 8个移动方向
int dir[8][2] = {{-1,-1},{-1,0},{-1,1},
                 {0,-1},        {0,1},
                 {1,-1}, {1,0},{1,1}};

const int MAXN = 8;
int n, m;                // n行m列
int grid[MAXN][MAXN];    // 1封锁，0可走
int sx, sy, ex, ey;      // 起点(sx,sy) 终点(ex,ey)
int total = 0;           // 需要走完的空房间总数
int vis_record[MAXN][MAXN][8][1<<25]; // 状态剪枝：xy+来向+访问掩码

struct Node {
    int x, y;
    int pre_dir;   // 上一步方向 -1起点
    int turn;      // 转弯次数
    int mask;      // 位图记录走过的格子

    // 优先队列：转弯小优先
    bool operator>(const Node& other) const {
        return turn > other.turn;
    }
};

// 坐标转编号：扁平化格子下标
inline int getid(int x,int y) {
    return x*m + y;
}

int bfs() {
    priority_queue<Node, vector<Node>, greater<Node>> q;
    memset(vis_record, 0x3f, sizeof(vis_record));

    Node st;
    st.x = sx; st.y = sy;
    st.pre_dir = -1;
    st.turn = 0;
    int id = getid(sx,sy);
    st.mask = 1 << id;

    q.push(st);
    vis_record[sx][sy][0][st.mask] = 0;

    while (!q.empty()) {
        auto cur = q.top();
        q.pop();

        // 全部走完且抵达终点，返回答案
        if (__builtin_popcount(cur.mask) == total && cur.x == ex && cur.y == ey) {
            return cur.turn;
        }

        for (int d = 0; d < 8; d++) {
            int nx = cur.x + dir[d][0];
            int ny = cur.y + dir[d][1];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(grid[nx][ny]==1) continue; // 封闭格子不能走
            int nid = getid(nx,ny);
            if((cur.mask & (1<<nid)) !=0) continue; // 已经走过

            Node nex = cur;
            nex.x = nx; nex.y = ny;
            nex.mask |= (1<<nid);

            // 计算转弯
            if(cur.pre_dir == -1) {
                nex.turn = cur.turn;
            } else if(d != cur.pre_dir) {
                nex.turn = cur.turn + 1;
            } else {
                nex.turn = cur.turn;
            }
            nex.pre_dir = d;

            // 状态剪枝：同位置同方向同掩码，已有更优解则不入队
            if(nex.turn < vis_record[nx][ny][d][nex.mask]) {
                vis_record[nx][ny][d][nex.mask] = nex.turn;
                q.push(nex);
            }
        }
    }
    return -1; // 无解
}

int main() {
    cin >> n >> m;
    total = 0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> grid[i][j];
            if(grid[i][j]==0) total++;
        }
    }
    cin >> sx >> sy >> ex >> ey;
    cout << bfs() << endl;
    return 0;
}