解法一：
#include <bits/stdc++.h> using namespace std; int main() { // n,m: 地图尺寸(n行m列)；k: 幽灵数量；inf: 无穷大（初始化最短时间） int n,m,k,inf = 1e9; cin>>n>>m>>k;
// a[x][y]: 位运算存储(x,y)是否有幽灵的奇偶位置
// a[x][y] |= 1 → (x,y)是某幽灵的奇数秒位置(x1i,y1i)
// a[x][y] |= 2 → (x,y)是某幽灵的偶数秒位置(x2i,y2i)
vector<vector<int>> a(n+1,vector<int>(m+1));
// b[x][y].first: 未使用时停到达(x,y)的最短时间
// b[x][y].second: 已使用时停到达(x,y)的最短时间
// 初始化为inf表示未到达
vector<vector<pair<int,int>>> b(n+1,vector<pair<int,int>>(m+1,{inf,inf}));
// 输入k个幽灵的奇偶位置，并标记到a数组
for(int i=1;i<=k;i++) {
int a1,a2,a3,a4; // a1,a2=x1i,y1i（奇数秒位置）；a3,a4=x2i,y2i（偶数秒位置）
cin>>a1>>a2>>a3>>a4;
a[a1][a2] |= 1; // 标记奇数秒位置
a[a3][a4] |= 2; // 标记偶数秒位置
}
// 优先队列元素类型：tuple<int,int,int,int> → (time, stop_time, x, y)
// time: 当前时间（从1开始）；stop_time: 时停触发时间（-1表示未使用时停）
// x,y: 当前坐标；小根堆（greater<str>）保证优先处理时间更短的状态（Dijkstra核心）
using str = tuple<int,int,int,int>;
priority_queue<str,vector<str>,greater<str>> q;
// 初始状态：时间1，未使用时停(stop_time=-1)，位置(1,1)（咲夜初始位置）
q.push({1,-1,1,1});
// 四个移动方向：右、下、左、上
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
// Dijkstra主循环：处理优先队列中的状态
while(!q.empty()) {
// 取出当前时间最短的状态：t=time, u=stop_time, x=x坐标, y=y坐标
auto [t,u,x,y] = q.top();
q.pop();
// 剪枝：如果当前状态的时间已超过记录的最短时间，跳过（避免重复处理）
if(u == -1) { // 未使用时停
if(b[x][y].first <= t) continue;
} else { // 已使用时停
if(b[x][y].second <= t) continue;
}
// a[x][y]==3 → 该位置同时是幽灵的奇数+偶数位置，绝对无法停留，跳过
if(a[x][y] == 3) continue;
// ok: 标记当前位置(x,y)在时间t是否安全（无幽灵）
bool ok = 1;
if(a[x][y]) { // 该位置有幽灵的奇偶位置记录，需要进一步判断
// 时停窗口期：stop_time == t 或 stop_time == t+1（时停持续2秒，幽灵位置固定）
if(u == t+1 || u == t) {
// 时停期间：偶数秒停→检查偶数位标记；奇数秒停→检查奇数位标记
if(u%2 == 0 && (a[x][y]&2)) ok = 0; // 时停触发时间偶→幽灵在偶数位
if(u%2 && (a[x][y] & 1)) ok =0; // 时停触发时间奇→幽灵在奇数位
} else {
// 非时停期间：时间t的奇偶性与幽灵位置标记匹配→有幽灵，不安全
if(a[x][y] % 2 == t%2) ok = 0;
}
}
// 当前位置不安全，跳过该状态
if(!ok) continue;
// 更新最短时间：记录到达(x,y)的最短时间
if(u == -1) { // 未使用时停
b[x][y].first = t;
} else { // 已使用时停
b[x][y].second = t;
}
// 到达终点(n,m)，直接退出循环（优先队列保证此时是最短时间）
if(x == n && y == m) {
break;
}
// 遍历四个移动方向，生成新状态
for(int i=0;i<4;i++) {
int tx = x + dx[i]; // 新x坐标
int ty = y + dy[i]; // 新y坐标
// 边界检查：坐标超出地图范围，跳过
if(tx <1 || ty < 1 || tx > n || ty > m) continue;
// 状态1：不使用时停，移动到(tx,ty)，时间+1
q.push({t+1,u,tx,ty});
// 状态2：使用时停（仅当未使用过时停时，u=-1），触发时间为t+2（持续2秒）
if(u == -1) q.push({t+1,t+2,tx,ty});
}
}
// 结果处理：如果两种状态都无法到达终点，输出-1；否则取最小值（时间偏移-1修正）
if(b[n][m].first == inf && b[n][m].second == inf) cout<<"-1\n";
else cout<<min(b[n][m].first,b[n][m].second)-1<<endl;
} 核心思路是Dijkstra 算法 + 时停状态记录 + 幽灵位置位运算判断
解法二：
#include #include #include #include <unordered_set> #include using namespace std;
typedef long long ll; const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; const int INF = 1e9;
struct Ghost { int x1, y1, x2, y2; };
struct Node { int x, y, time, stop_used, stop_rem, h; bool operator>(const Node& other) const { return (time + h) > (other.time + other.h); } };
// 纯整数运算，避免浮点转换 int cal_h(int x, int y, int n, int m) { return (n - x) + (m - y); // 曼哈顿距离，无浮点 }
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<Ghost> ghosts(k);
unordered_set<ll> ghost_pos[2];
// 编码函数：强制所有运算为ll，避免int溢出
auto encode = [&](int x, int y) -> ll {
ll xl = static_cast<ll>(x);
ll ml = static_cast<ll>(m + 2);
ll yl = static_cast<ll>(y);
return xl * ml + yl;
};
// 读取幽灵参数：严格整数读取，避免格式错误
for (int i = 0; i < k; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
ghosts[i] = {x1, y1, x2, y2};
ghost_pos[0].insert(encode(x1, y1));
ghost_pos[1].insert(encode(x2, y2));
}
priority_queue<Node, vector<Node>, greater<Node>> pq;
// 优化距离数组初始化：避免维度越界
vector<vector<vector<vector<int>>>> dist(
n + 2, vector<vector<vector<int>>>(
m + 2, vector<vector<int>>(2, vector<int>(3, INF))
)
);
int init_h = cal_h(1, 1, n, m);
dist[1][1][0][0] = 0;
pq.push({1, 1, 0, 0, 0, init_h});
int ans = INF;
while (!pq.empty()) {
Node cur = pq.top();
pq.pop();
if (cur.x == n && cur.y == m) {
ans = cur.time;
break;
}
if (cur.time > dist[cur.x][cur.y][cur.stop_used][cur.stop_rem]) {
continue;
}
int next_time = cur.time + 1;
int ghost_state = next_time % 2;
int cur_stop_rem = cur.stop_rem;
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// 严格边界检查：避免负数坐标
if (nx < 1 || nx > n || ny < 1 || ny > m) {
continue;
}
for (int use_stop = 0; use_stop <= 1; use_stop++) {
if (use_stop && cur.stop_used) {
continue;
}
int new_stop_rem = cur_stop_rem;
if (use_stop) {
new_stop_rem = 2;
} else if (cur_stop_rem > 0) {
new_stop_rem--;
}
ll pos_code = encode(nx, ny);
bool safe = true;
if (new_stop_rem > 0) {
// 避免负数取模：(a % 2 + 2) % 2 保证结果为0/1
int fixed_state = (next_time - new_stop_rem) % 2;
fixed_state = (fixed_state + 2) % 2;
safe = (ghost_pos[fixed_state].count(pos_code) == 0);
} else {
safe = (ghost_pos[ghost_state].count(pos_code) == 0);
}
if (!safe) {
continue;
}
int new_stop_used = cur.stop_used | use_stop;
// ========== 核心优化：入队前检查 ==========
// 只有当新时间确实更优时，才更新距离并加入队列
if (next_time < dist[nx][ny][new_stop_used][new_stop_rem]) {
dist[nx][ny][new_stop_used][new_stop_rem] = next_time;
int new_h = cal_h(nx, ny, n, m);
pq.push({nx, ny, next_time, new_stop_used, new_stop_rem, new_h});
}
// =======================================
}
}
}
cout << (ans == INF ? -1 : ans) << endl; // 简化输出，避免多次cout
return 0;
} 关键数据结构： 结构 / 变量作用（核心是 “快速查询 + 状态记录”） ghost_pos[0/1]：哈希集合，O(1) 查询位置是否有幽灵：
- ghost_pos[0]：奇数秒幽灵位置（编码后）；
- ghost_pos[1]：偶数秒幽灵位置（编码后） encode(x,y)坐标转 long long：x*(m+2)+y，避免二维坐标冲突 + int 溢出，适配哈希集合 struct Node A* 节点，包含： x,y：当前坐标； time：已用时间； stop_used：是否用过时停（0/1）； stop_rem：时停剩余时长（0/1/2）； h：曼哈顿启发距离 dist[x][y][2][3]：距离数组，记录 “到达 (x,y) + 时停状态（stop_used） + 时停剩余（stop_rem）” 的最短时间，初始为 INF（未到达）
京公网安备 11010502036488号